101,960 research outputs found
Nordhaus-Gaddum for treewidth
No full textWe prove that, for every n-vertex graph G, the treewidth of G plus the treewidth of the complement of G is at least n- 2. This bound is tight. © 2012 Gwenaël Joret and David R. Wood.SCOPUS: ar.jinfo:eu-repo/semantics/publishe
Du G dans les langues romanes, par Ch. Joret, 1874
No full textDarmesteter Arsène. Du G dans les langues romanes, par Ch. Joret, 1874. In: Romania, tome 3 n°11, 1874. pp. 379-398
Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
No full textLet G be a connected n-vertex graph in a proper minor-closed class G. We prove that the extension complexity of the spanning tree polytope of G is O(n3/2). This improves on the O(n2) bounds following from the work of Wong (1980) and Martin (1991). It also extends a result of Fiorini, Huynh, Joret, and Pashkovich (2017), who obtained a O(n3/2) bound for graphs embedded in a fixed surface. Our proof works more generally for all graph classes admitting strongly sublinear balanced separators: We prove that for every constant β with 0 < β < 1, if G is a graph class closed under induced subgraphs such that all n-vertex graphs in G have balanced separators of size O(nβ ), then the extension complexity of the spanning tree polytope of every connected n-vertex graph in G is O(n1+β ). We in fact give two proofs of this result, one is a direct construction of the extended formulation, the other is via communication protocols. Using the latter approach we also give a short proof of the O(n) bound for planar graphs due to Williams (2002)
Anecdota Oxoniensia. Texts, documents, and extracts, chiefly from manuscrits in the Bodleian and other Oxford libraries. Vol. I Part II. — Alphita edited by J. L. G. Mowat, M. A. Oxford, 1887
No full textJoret Charles. Anecdota Oxoniensia. Texts, documents, and extracts, chiefly from manuscrits in the Bodleian and other Oxford libraries. Vol. I Part II. — Alphita edited by J. L. G. Mowat, M. A. Oxford, 1887. In: Romania, tome 16 n°62-64, 1887. pp. 598-602
Anecdota Oxoniensia. Texts, documents, and extracts, chiefly from manuscrits in the Bodleian and other Oxford libraries. Vol. I Part II. — Alphita edited by J. L. G. Mowat, M. A. Oxford, 1887
No full textJoret Charles. Anecdota Oxoniensia. Texts, documents, and extracts, chiefly from manuscrits in the Bodleian and other Oxford libraries. Vol. I Part II. — Alphita edited by J. L. G. Mowat, M. A. Oxford, 1887. In: Romania, tome 16 n°62-64, 1887. pp. 598-602
Unavoidable minors for graphs with large l_p-dimension
No full textA \emph{metric graph} is a pair , where is a graph and is a distance function. Let be fixed. An \emph{isometric embedding} of the metric graph in is a map such that for all edges . The \emph{-dimension} of is the least integer such that there exists an isometric embedding of in for all distance functions such that has an isometric embedding in for some .
It is easy to show that -dimension is a minor-monotone property.
In this paper, we characterize the minor-closed graph classes with bounded -dimension, for .
For , we give a simple proof that has bounded -dimension if and only if has bounded treewidth.
In this sense, the -dimension of a graph is `tied' to its treewidth.
For , the situation is completely different.
Our main result states that a minor-closed class has bounded -dimension if and only if excludes a graph obtained by joining copies of using the -sum operation, or excludes a M\"obius ladder with one `horizontal edge' removed
Smaller Extended Formulations for the Spanning Tree Polytope of Bounded-Genus Graphs
No full textWe give an O(g1 / 2n3 / 2+ g3 / 2n1 / 2) -size extended formulation for the spanning tree polytope of an n-vertex graph embedded in a surface of genus g, improving on the known O(n2+ gn) -size extended formulations following from Wong (Proceedings of 1980 IEEE International Conference on Circuits and Computers, pp 149–152, 1980) and Martin (Oper Res Lett 10:119–128, 1991)
Excluding a Ladder
No full textA ladder is a 2xk grid graph. When does a graph class C exclude some ladder as a minor? We show that this is the case if and only if all graphs G in C admit a proper vertex coloring with a bounded number of colors such that for every 2-connected subgraph H of G, there is a color that appears exactly once in H. This type of vertex coloring is a relaxation of the notion of centered coloring, where for every connected subgraph H of G, there must be a color that appears exactly once in H. The minimum number of colors in a centered coloring of G is the treedepth of G, and it is known that classes of graphs with bounded treedepth are exactly those that exclude a fixed path as a subgraph, or equivalently, as a minor. In this sense, the structure of graphs excluding a fixed ladder as a minor resembles the structure of graphs without long paths. Another similarity is as follows: It is an easy observation that every connected graph with two vertex-disjoint paths of length k has a path of length k + 1. We show that every 3-connected graph which contains as a minor a union of sufficiently many vertex-disjoint copies of a 2 x k grid has a 2x(k + 1) grid minor.Our structural results have applications to poset dimension. We show that posets whose cover graphs exclude a fixed ladder as a minor have bounded dimension. This is a new step towards the goal of understanding which graphs are unavoidable as minors in cover graphs of posets with large dimension
Two lower bounds for p-centered colorings
No full textGiven a graph G and an integer p, a coloring f :V (G) N is p-centered if for every connected subgraph H of G, either f uses more than p colors on H or there is a color that appears exactly once in H. The notion of p-centered colorings plays a central role in the theory of sparse graphs. In this note we show two lower bounds on the number of colors required in a p-centered coloring. First, we consider monotone classes of graphs whose shallow minors have average degree bounded polynomially in the radius, or equivalently (by a result of Dvǒrák and Norin), admitting strongly sublinear separators. We construct such a class such that p-centered colorings require a number of colors super-polynomial in p. This is in contrast with a recent result of Pilipczuk and Siebertz, who established a polynomial upper bound in the special case of graphs excluding a fixed minor. Second, we consider graphs of maximum degree. Debski, Felsner, Micek, and Schröder recently proved that these graphs have p-centered colorings with O(21=pp) colors. We show that there are graphs of maximum degree that require (21=pp ln1=p) colors in any p-centered coloring, thus matching their upper bound up to a logarithmic factor.SCOPUS: ar.jinfo:eu-repo/semantics/publishe
Tight bound for the Erd\H{o}s-P\'osa property of tree minors
No full textLet be a tree on vertices. We prove that for every positive integer
and every graph , either contains pairwise vertex-disjoint
subgraphs each having a minor, or there exists a set of at most
vertices of such that has no minor. The bound on the
size of is best possible and improves on an earlier bound proved by
Fiorini, Joret, and Wood (2013) with some very fast growing function .
Moreover, our proof is very short and simple
- …
