BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We prove that for every tree T of radius h, there is an integer c such that every T-minor-free graph is contained in H⊠Kc for some graph H with pathwidth at most 2h−1. This is a qualitative strengthening of the Excluded Tree Minor Theorem of Robertson and Seymour (GM I). We show that radius is the right parameter to consider in this setting, and 2h−1 is the best possible bound.
We determine which properties of 2-layer drawings characterise bipartite graphs of bounded pathwidth.
The "clustered chromatic number" of a class of graphs is the minimum integer k such that for some integer c every graph in the class is k-colourable with monochromatic components of size at most c. We determine the clustered chromatic number of any minor-closed class with bounded treedepth, and prove a best possible upper bound on the clustered chromatic number of any minor-closed class with bounded pathwidth. As a consequence, we determine the fractional clustered chromatic number of every minor-closed class.
We prove that the vertices of every (r+1)-uniform hypergraph with maximum degree Δ may be coloured with c(d+1Δ)1/r colours such that each vertex is in at most d monochromatic edges. This result, which is best possible up to the value of the constant c, generalises the classical result of Erdős and Lovász who proved the d=0 case.
The "extremal function" c(H) of a graph H is the supremum of densities of graphs not containing H as a minor, where the "density" of a graph G is the ratio of the number of edges to the number of vertices. Myers and Thomason (2005), Norin, Reed, Thomason and Wood (2020), and Thomason and Wales (2019) determined the asymptotic behaviour of c(H) for all polynomially dense graphs H, as well as almost all graphs H of constant density. We explore the asymptotic behavior of the extremal function in the regime not covered by the above results, where in addition to having constant density the graph H is in a graph class admitting strongly sublinear separators. We establish asymptotically tight bounds in many cases. For example, we prove that for every planar graph H, c(H)=(1+o(1))⋅max{2∣V(H)∣,∣V(H)∣−α(H)}, extending recent results of Haslegrave, Kim and Liu (2020). We also show that an asymptotically tight bound on the extremal function of graphs in minor-closed families proposed by Haslegrave, Kim and Liu (2020) is equivalent to a well studied open weakening of Hadwiger's conjecture.
We answer three questions posed by Bubeck and Linial on the limit densities of subtrees in trees. We prove there exist positive ε1 and ε2 such that every tree that is neither a path nor a star has inducibility at most 1−ε1, where the inducibility of a tree T is defined as the maximum limit density of T, and that there are infinitely many trees with inducibility at least ε2. Finally, we construct a universal sequence of trees; that is, a sequence in which the limit density of any tree is positive.
A colouring of a graph is "nonrepetitive" if for every path of even order, the sequence of colours on the first half of the path is different from the sequence of colours on the second half. We show that planar graphs have nonrepetitive colourings with a bounded number of colours, thus proving a conjecture of Alon, Grytczuk, Haluszczak and Riordan (2002). We also generalise this result for graphs of bounded Euler genus, graphs excluding a fixed minor, and graphs excluding a fixed topological minor.
We show that many graphs with bounded treewidth can be described as subgraphs of the strong product of a graph with smaller treewidth and a bounded-size complete graph. To this end, define the "underlying treewidth" of a graph class G to be the minimum non-negative integer c such that, for some function f, for every graph G∈G there is a graph H with tw(H)≤c such that G is isomorphic to a subgraph of H⊠Kf(tw(G)). We introduce disjointed coverings of graphs and show they determine the underlying treewidth of any graph class. Using this result, we prove that the class of planar graphs has underlying treewidth 3; the class of Ks,t-minor-free graphs has underlying treewidth s (for t≥max{s,3}); and the class of Kt-minor-free graphs has underlying treewidth t−2. In general, we prove that a monotone class has bounded underlying treewidth if and only if it excludes some fixed topological minor. We also study the underlying treewidth of graph classes defined by an excluded subgraph or excluded induced subgraph. We show that the class of graphs with no H subgraph has bounded underlying treewidth if and only if every component of H is a subdivided star, and that the class of graphs with no induced H subgraph has bounded underlying treewidth if and only if every component of H is a star.
The planar graph product structure theorem of Dujmović, Joret, Micek, Morin, Ueckerdt, and Wood [J. ACM 2020] states that every planar graph is a subgraph of the strong product of a graph with bounded treewidth and a path. This result has been the key tool to resolve important open problems regarding queue layouts, nonrepetitive colourings, centered colourings, and adjacency labelling schemes. In this paper, we extend this line of research by utilizing shallow minors to prove analogous product structure theorems for several beyond planar graph classes. The key observation that drives our work is that many beyond planar graphs can be described as a shallow minor of the strong product of a planar graph with a small complete graph. In particular, we show that powers of planar graphs, k-planar, (k,p)-cluster planar, fan-planar and k-fan-bundle planar graphs have such a shallow-minor structure. Using a combination of old and new results, we deduce that these classes have bounded queue-number, bounded nonrepetitive chromatic number, polynomial p-centred chromatic numbers, linear strong colouring numbers, and cubic weak colouring numbers. In addition, we show that k-gap planar graphs have at least exponential local treewidth and, as a consequence, cannot be described as a subgraph of the strong product of a graph with bounded treewidth and a path.
A squaregraph is a plane graph in which each internal face is a 4-cycle and each internal vertex has degree at least 4. This paper proves that every squaregraph is isomorphic to a subgraph of the semi-strong product of an outerplanar graph and a path. We generalise this result for infinite squaregraphs, and show that this is best possible in the sense that "outerplanar graph" cannot be replaced by "forest".
We describe a family of graphs with queue-number at most 4 but unbounded stack-number. This resolves open problems of Heath, Leighton and Rosenberg (1992) and Blankenship and Oporowski (1999).
We prove that a minor-closed class of graphs has bounded layered pathwidth if and only if some apex-forest is not in the class. This generalises a theorem of Robertson and Seymour, which says that a minor-closed class of graphs has bounded pathwidth if and only if some forest is not in the class.
It was recently proved that every planar graph is a subgraph of the strong product of a path and a graph with bounded treewidth. This paper surveys generalisations of this result for graphs on surfaces, minor-closed classes, various non-minor-closed classes, and graph classes with polynomial growth. We then explore how graph product structure might be applicable to more broadly defined graph classes. In particular, we characterise when a graph class defined by a cartesian or strong product has bounded or polynomial expansion. We then explore graph product structure theorems for various geometrically defined graph classes, and present several open problems.
Tree-chromatic number is a chromatic version of treewidth, where the cost of a bag in a tree-decomposition is measured by its chromatic number rather than its size. Path-chromatic number is defined analogously. These parameters were introduced by Seymour (JCTB 2016). In this paper, we survey all the known results on tree- and path-chromatic number and then present some new results and conjectures. In particular, we propose a version of Hadwiger's Conjecture for tree-chromatic number. As evidence that our conjecture may be more tractable than Hadwiger's Conjecture, we give a short proof that every K5-minor-free graph has tree-chromatic number at most 4, which avoids the Four Colour Theorem. We also present some hardness results and conjectures for computing tree- and path-chromatic number.
We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath, Leighton and Rosenberg from 1992. The key to the proof is a new structural tool called layered partitions, and the result that every planar graph has a vertex-partition and a layering, such that each part has a bounded number of vertices in each layer, and the quotient graph has bounded treewidth. This result generalises for graphs of bounded Euler genus. Moreover, we prove that every graph in a minor-closed class has such a layered partition if and only if the class excludes some apex graph. Building on this work and using the graph minor structure theorem, we prove that every proper minor-closed class of graphs has bounded queue-number. Layered partitions have strong connections to other topics, including the following two examples. First, they can be interpreted in terms of strong products. We show that every planar graph is a subgraph of the strong product of a path with some graph of bounded treewidth. Similar statements hold for all proper minor-closed classes. Second, we give a simple proof of the result by DeVos et al. (2004) that graphs in a proper minor-closed class have low treewidth colourings.
We prove the conjecture of Seymour (1993) that for every apex-forest H1 and outerplanar graph H2 there is an integer p such that every 2-connected graph of pathwidth at least p contains H1 or H2 as a minor. An independent proof was recently obtained by Dang and Thomas.
We prove that the dimension of every poset whose comparability graph has maximum degree Δ is at most Δlog1+o(1)Δ. This result improves on a 30-year old bound of Füredi and Kahn, and is within a logo(1)Δ factor of optimal. We prove this result via the notion of boxicity. The "boxicity" of a graph G is the minimum integer d such that G is the intersection graph of d-dimensional axis-aligned boxes. We prove that every graph with maximum degree Δ has boxicity at most Δlog1+o(1)Δ, which is also within a logo(1)Δ factor of optimal. We also show that the maximum boxicity of graphs with Euler genus g is Θ(glogg), which solves an open problem of Esperet and Joret and is tight up to a O(1) factor.
Motivated by the study of the crossing number of graphs, it is shown that, for trees, the sum of the products of the degrees of the end-vertices of all edges has an upper bound in terms of the sum of all vertex degrees to the power of ϕ2, where ϕ is the golden ratio. The exponent ϕ2 is best possible. This inequality is generalized for all graphs with bounded maximum average degree.
The "clustered chromatic number" of a class of graphs is the minimum integer k such that for some integer c every graph in the class is k-colourable with monochromatic components of size at most c. We prove that for every graph H, the clustered chromatic number of the class of H-minor-free graphs is tied to the tree-depth of H. In particular, if H is connected with tree-depth t then every H-minor-free graph is (2t+1−4)-colourable with monochromatic components of size at most c(H). This provides the first evidence for a conjecture of Ossona de Mendez, Oum and Wood (2016) about defective colouring of H-minor-free graphs. If t=3 then we prove that 4 colours suffice, which is best possible. We also determine those minor-closed graph classes with clustered chromatic number 2. Finally, we develop a conjecture for the clustered chromatic number of an arbitrary minor-closed class.
This paper considers the following question: What is the maximum number of k-cliques in an n-vertex graph with no Kt-minor? This question generalises the extremal function for Kt-minors, which corresponds to the k=2 case. The exact answer is given for t≤9 and all values of k. We also determine the maximum total number of cliques in an n-vertex graph with no Kt-minor for t≤9. Several observations are made about the case of general t.
In this paper we define and study a new family of graphs that generalises the notions of line graphs and path graphs. Let G be a graph with no loops but possibly with parallel edges. An \emph{ℓ-link} of G is a walk of G of length ℓ⩾0 in which consecutive edges are different. We identify an ℓ-link with its reverse sequence. The \emph{ℓ-link graph Lℓ(G)} of G is the graph with vertices the ℓ-links of G, such that two vertices are joined by μ⩾0 edges in Lℓ(G) if they correspond to two subsequences of each of μ (ℓ+1)-links of G. By revealing a recursive structure, we bound from above the chromatic number of ℓ-link graphs. As a corollary, for a given graph G and large enough ℓ, Lℓ(G) is 3-colourable. By investigating the shunting of ℓ-links in G, we show that the Hadwiger number of a nonempty Lℓ(G) is greater or equal to that of G. Hadwiger's conjecture states that the Hadwiger number of a graph is at least the chromatic number of that graph. The conjecture has been proved by Reed and Seymour (2004) for line graphs, and hence 1-link graphs. We prove the conjecture for a wide class of ℓ-link graphs.
Bourgain and Yehudayoff recently constructed O(1)-monotone bipartite expanders. By combining this result with a generalisation of the unraveling method of Kannan, we construct 3-monotone bipartite expanders, which is best possible. We then show that the same graphs admit 3-page book embeddings, 2-queue layouts, 4-track layouts, and have simple thickness 2. All these results are best possible.
Treewidth is a graph parameter of fundamental importance to algorithmic and structural graph theory. This paper surveys several graph parameters tied to treewidth, including separation number, tangle number, well-linked number and Cartesian tree product number. We review many results in the literature showing these parameters are tied to treewidth. In a number of cases we also improve known bounds, provide simpler proofs and show that the inequalities presented are tight.
We prove that for every graph G, given fixed locations for the vertices of G in Z3, there is a three-dimensional grid-drawing of G with one bend per edge. The best previous bound was three bends per edge.
We generalise a result of Corrádi and Hajnal and show that every graph with average degree at least 34kr contains k vertex disjoint cycles, each of order at least r, as long as k≥6. This bound is sharp when r=3.
Consider a drawing of a graph G in the plane such that crossing edges are coloured differently. The minimum number of colours, taken over all drawings of G, is the classical graph parameter "thickness". By restricting the edges to be straight, we obtain the "geometric thickness". By further restricting the vertices to be in convex position, we obtain the "book thickness". This paper studies the relationship between these parameters and treewidth. Our first main result states that for graphs of treewidth k, the maximum thickness and the maximum geometric thickness both equal ⌈k/2⌉. This says that the lower bound for thickness can be matched by an upper bound, even in the more restrictive geometric setting. Our second main result states that for graphs of treewidth k, the maximum book thickness equals k if k≤2 and equals k+1 if k≥3. This refutes a conjecture of Ganley and Heath [Discrete Appl. Math. 109(3):215-221, 2001]. Analogous results are proved for outerthickness, arboricity, and star-arboricity.
The maximum number of vertices in a graph of maximum degree Δ≥3 and fixed diameter k≥2 is upper bounded by (1+o(1))(Δ−1)k. If we restrict our graphs to certain classes, better upper bounds are known. For instance, for the class of trees there is an upper bound of (2+o(1))(Δ−1)⌊k/2⌋ for a fixed k. The main result of this paper is that graphs embedded in surfaces of bounded Euler genus g behave like trees, in the sense that, for large Δ, such graphs have orders bounded from above by \[begin{cases} c(g+1)(Δ-1)^{\lfloor k/2\rfloor} & \text{if $k$ is even} c(g^{3/2}+1)(Δ-1)^{\lfloor k/2\rfloor} & \text{if $k$ is odd}, \{cases}\] where c is an absolute constant. This result represents a qualitative improvement over all previous results, even for planar graphs of odd diameter k. With respect to lower bounds, we construct graphs of Euler genus g, odd diameter k, and order c(g+1)(Δ−1)⌊k/2⌋ for some absolute constant c>0. Our results answer in the negative a question of Miller and Širáň (2005).
Brooks' Theorem [R. L. Brooks, On Colouring the Nodes of a Network, Proc. Cambridge Philos. Soc.} 37:194-197, 1941] states that every graph G with maximum degree Δ, has a vertex-colouring with Δ colours, unless G is a complete graph or an odd cycle, in which case Δ+1 colours are required. Lovász [L. Lovász, Three short proofs in graph theory, J. Combin. Theory Ser. 19:269-271, 1975] gives an algorithmic proof of Brooks' Theorem. Unfortunately this proof is missing important details and it is thus unclear whether it leads to a linear time algorithm. In this paper we give a complete description of the proof of Lovász, and we derive a linear time algorithm for determining the vertex-colouring guaranteed by Brooks' Theorem.
Birmele [J. Graph Theory, 2003] proved that every graph with circumference t has treewidth at most t-1. Under the additional assumption of 2-connectivity, such graphs have bounded pathwidth, which is a qualitatively stronger result. Birmele's theorem was extended by Birmele, Bondy and Reed [Combinatorica, 2007] who showed that every graph without k disjoint cycles of length at least t has bounded treewidth (as a function of k and t). Our main result states that, under the additional assumption of (k + 1)- connectivity, such graphs have bounded pathwidth. In fact, they have pathwidth O(t^3 + tk^2). Moreover, examples show that (k + 1)-connectivity is required for bounded pathwidth to hold. These results suggest the following general question: for which values of k and graphs H does every k-connected H-minor-free graph have bounded pathwidth? We discuss this question and provide a few observations.
Erdős asked what is the maximum number α(n) such that every set of n points in the plane with no four on a line contains α(n) points in general position. We consider variants of this question for d-dimensional point sets and generalize previously known bounds. In particular, we prove the following two results for fixed d: - Every set H of n hyperplanes in Rd contains a subset S⊆H of size at least c(nlogn)1/d, for some constant c=c(d)>0, such that no cell of the arrangement of H is bounded by hyperplanes of S only. - Every set of cqdlogq points in Rd, for some constant c=c(d)>0, contains a subset of q cohyperplanar points or q points in general position. Two-dimensional versions of the above results were respectively proved by Ackerman et al. [Electronic J. Combinatorics, 2014] and by Payne and Wood [SIAM J. Discrete Math., 2013].
A hypergraph is "d-degenerate" if every subhypergraph has a vertex of degree at most d. A greedy algorithm colours every such hypergraph with at most d+1 colours. We show that this bound is tight, by constructing an r-uniform d-degenerate hypergraph with chromatic number d+1 for all r≥2 and d≥1. Moreover, the hypergraph is triangle-free, where a "triangle" in an r-uniform hypergraph consists of three edges whose union is a set of r+1 vertices.
The treewidth of a graph is an important invariant in structural and algorithmic graph theory. This paper studies the treewidth of line graphs. We show that determining the treewidth of the line graph of a graph G is equivalent to determining the minimum vertex congestion of an embedding of G into a tree. Using this result, we prove sharp lower bounds in terms of both the minimum degree and average degree of G. These results are precise enough to exactly determine the treewidth of the line graph of a complete graph and other interesting examples. We also improve the best known upper bound on the treewidth of a line graph. Analogous results are proved for pathwidth.
In recent papers by Grohe and Marx, the treewidth of the line graph of the complete graph is a critical example. We determine the exact treewidth of the line graph of the complete graph. By extending these techniques, we determine the exact treewidth of the line graph of a regular complete multipartite graph. For an arbitrary complete multipartite graph, we determine the treewidth of the line graph up to a lower order term.
Let g(t) be the minimum number such that every graph G with average degree d(G) \geq g(t) contains a K_{t}-minor. Such a function is known to exist, as originally shown by Mader. Kostochka and Thomason independently proved that g(t) \in Θ(t*sqrt{log t}). This article shows that for all fixed ε> 0 and fixed sufficiently large t \geq t(ε), if d(G) \geq (2+ε)g(t) then we can find this K_{t}-minor in linear time. This improves a previous result by Reed and Wood who gave a linear-time algorithm when d(G) \geq 2^{t-2}.
Hadwiger's Conjecture states that every Kt+1-minor-free graph is t-colourable. It is widely considered to be one of the most important conjectures in graph theory. If every Kt+1-minor-free graph has minimum degree at most δ, then every Kt+1-minor-free graph is (δ+1)-colourable by a minimum-degree-greedy algorithm. The purpose of this note is to prove a slightly better upper bound.
A classical result of Robertson and Seymour states that the set of graphs containing a fixed planar graph H as a minor has the so-called Erdős-Pósa property; namely, there exists a function f depending only on H such that, for every graph G and every positive integer k, the graph G has k vertex-disjoint subgraphs each containing H as a minor, or there exists a subset X of vertices of G with ∣X∣≤f(k) such that G−X has no H-minor. While the best function f currently known is exponential in k, a O(klogk) bound is known in the special case where H is a forest. This is a consequence of a theorem of Bienstock, Robertson, Seymour, and Thomas on the pathwidth of graphs with an excluded forest-minor. In this paper we show that the function f can be taken to be linear when H is a forest. This is best possible in the sense that no linear bound is possible if H has a cycle.
In 1951, Gabriel Dirac conjectured that every set P of n non-collinear points in the plane contains a point in at least n/2-c lines determined by P, for some constant c. The following weakening was proved by Beck and Szemerédi-Trotter: every set P of n non-collinear points contains a point in at least n/c lines determined by P, for some large unspecified constant c. We prove that every set P of n non-collinear points contains a point in at least n/37 lines determined by P. We also give the best known constant for Beck's Theorem, proving that every set of n points with at most k collinear determines at least n(n-k)/98 lines.
We prove a new sufficient condition for a cubic 3-connected planar graph to be Hamiltonian. This condition is most easily described as a property of the dual graph. Let G be a planar triangulation. Then the dual G∗ is a cubic 3-connected planar graph, and G∗ is bipartite if and only if G is Eulerian. We prove that if the vertices of G are (improperly) coloured blue and red, such that the blue vertices cover the faces of G, there is no blue cycle, and every red cycle contains a vertex of degree at most 4, then G∗ is Hamiltonian. This result implies the following special case of Barnette's Conjecture: if G is an Eulerian planar triangulation, whose vertices are properly coloured blue, red and green, such that every red-green cycle contains a vertex of degree 4, then G∗ is Hamiltonian. Our final result highlights the limitations of using a proper colouring of G as a starting point for proving Barnette's Conjecture. We also explain related results on Barnette's Conjecture that were obtained by Kelmans and for which detailed self-contained proofs have not been published.
Treewidth is an important and well-known graph parameter that measures the complexity of a graph. The Kneser graph Kneser(n,k) is the graph with vertex set (k[n]), such that two vertices are adjacent if they are disjoint. We determine, for large values of n with respect to k, the exact treewidth of the Kneser graph. In the process of doing so, we also prove a strengthening of the Erdős-Ko-Rado Theorem (for large n with respect to k) when a number of disjoint pairs of k-sets are allowed.
For k >= 3, a k-angulation is a 2-connected plane graph in which every internal face is a k-gon. We say that a point set P admits a plane graph G if there is a straight-line drawing of G that maps V(G) onto P and has the same facial cycles and outer face as G. We investigate the conditions under which a point set P admits a k-angulation and find that, for sets containing at least 2k^2 points, the only obstructions are those that follow from Euler's formula.
It is known that the First-Fit algorithm for partitioning a poset P into chains uses relatively few chains when P does not have two incomparable chains each of size k. In particular, if P has width w then Bosek, Krawczyk, and Szczypka (SIAM J. Discrete Math., 23(4):1992--1999, 2010) proved an upper bound of ckw^{2} on the number of chains used by First-Fit for some constant c, while Joret and Milans (Order, 28(3):455--464, 2011) gave one of ck^{2}w. In this paper we prove an upper bound of the form ckw. This is best possible up to the value of c.
This paper is about: (1) bounds on the number of cliques in a graph in a particular class, and (2) algorithms for listing all cliques in a graph. We present a simple algorithm that lists all cliques in an n-vertex graph in O(n) time per clique. For O(1)-degenerate graphs, such as graphs excluding a fixed minor, we describe a O(n) time algorithm for listing all cliques. We prove that graphs excluding a fixed odd-minor have O(n2) cliques (which is tight), and conclude a O(n3) time algorithm for listing all cliques.
The graph minor structure theorem by Robertson and Seymour shows that every graph that excludes a fixed minor can be constructed by a combination of four ingredients: graphs embedded in a surface of bounded genus, a bounded number of vortices of bounded width, a bounded number of apex vertices, and the clique-sum operation. This paper studies the converse question: What is the maximum order of a complete graph minor in a graph constructed using these four ingredients? Our main result answers this question up to a constant factor.
Let k≥ℓ≥1 and n≥1 be integers. Let G(k,n) be the complete k-partite graph with n vertices in each colour class. An ℓ-decomposition of G(k,n) is a set X of copies of Kk in G(k,n) such that each copy of Kℓ in G(k,n) is a subgraph of exactly one copy of Kk in X. This paper asks: when does G(k,n) have an ℓ-decomposition? The answer is well known for the ℓ=2 case. In particular, G(k,n) has a 2-decomposition if and only if there exists k−2 mutually orthogonal Latin squares of order n. For general ℓ, we prove that G(k,n) has an ℓ-decomposition if and only if there are k−ℓ Latin cubes of dimension ℓ and order n, with an additional property that we call mutually invertible. This property is stronger than being mutually orthogonal. An ℓ-decomposition of G(k,n) is then constructed whenever no prime less than k divides n.
An empty pentagon in a point set P in the plane is a set of five points in P in strictly convex position with no other point of P in their convex hull. We prove that every finite set of at least 328k^2 points in the plane contains an empty pentagon or k collinear points. This is optimal up to a constant factor since the (k-1)x(k-1) grid contains no empty pentagon and no k collinear points. The previous best known bound was doubly exponential.
Fix integers b>a≥1 with g:=gcd(a,b). A set S⊆N is \emph{{a,b}-multiplicative} if ax=by for all x,y∈S. For all n, we determine an {a,b}-multiplicative set with maximum cardinality in [n], and conclude that the maximum density of an {a,b}-multiplicative set is b+gb. For A,B⊆N, a set S⊆N is \emph{{A,B}-multiplicative} if ax=by implies a=b and x=y for all a∈A and b∈B, and x,y∈S. For 1<a<b<c and a,b,c coprime, we give an O(1) time algorithm to approximate the maximum density of an {{a},{b,c}}-multiplicative set to arbitrary given precision.
Let f(n,ℓ) be the maximum integer such that every set of n points in the plane with at most ℓ collinear contains a subset of f(n,ℓ) points with no three collinear. First we prove that if ℓ≤O(n) then f(n,ℓ)≥Ω(lnℓn). Second we prove that if ℓ≤O(n(1−ε)/2) then f(n,ℓ)≥Ω(nlogℓn), which implies all previously known lower bounds on f(n,ℓ) and improves them when ℓ is not fixed. A more general problem is to consider subsets with at most k collinear points in a point set with at most ℓ collinear. We also prove analogous results in this setting.
A fundamental result in structural graph theory states that every graph with large average degree contains a large complete graph as a minor. We prove this result with the extra property that the minor is small with respect to the order of the whole graph. More precisely, we describe functions f and h such that every graph with n vertices and average degree at least f(t) contains a Kt-model with at most h(t)⋅logn vertices. The logarithmic dependence on n is best possible (for fixed t). In general, we prove that $f(t)\leq 2^{t-1}+\eps$. For t≤4, we determine the least value of f(t); in particular $f(3)=2+\eps$ and $f(4)=4+\eps$. For t≤4, we establish similar results for graphs embedded on surfaces, where the size of the Kt-model is bounded (for fixed t).
A "clique minor" in a graph G can be thought of as a set of connected subgraphs in G that are pairwise disjoint and pairwise adjacent. The "Hadwiger number" h(G) is the maximum cardinality of a clique minor in G. This paper studies clique minors in the Cartesian product G*H. Our main result is a rough structural characterisation theorem for Cartesian products with bounded Hadwiger number. It implies that if the product of two sufficiently large graphs has bounded Hadwiger number then it is one of the following graphs: - a planar grid with a vortex of bounded width in the outerface, - a cylindrical grid with a vortex of bounded width in each of the two `big' faces, or - a toroidal grid. Motivation for studying the Hadwiger number of a graph includes Hadwiger's Conjecture, which states that the chromatic number chi(G) <= h(G). It is open whether Hadwiger's Conjecture holds for every Cartesian product. We prove that if |V(H)|-1 >= chi(G) >= chi(H) then Hadwiger's Conjecture holds for G*H. On the other hand, we prove that Hadwiger's Conjecture holds for all Cartesian products if and only if it holds for all G * K_2. We then show that h(G * K_2) is tied to the treewidth of G. We also develop connections with pseudoachromatic colourings and connected dominating sets that imply near-tight bounds on the Hadwiger number of grid graphs (Cartesian products of paths) and Hamming graphs (Cartesian products of cliques).
Let P be a set of n points in general position in the plane. We study the chromatic number of the intersection graph of the open triangles determined by P. It is known that this chromatic number is at least n^3/27+O(n^2), and if P is in convex position, the answer is n^3/24+O(n^2). We prove that for arbitrary P, the chromatic number is at most n^3/19.259+O(n^2).
We prove that for every graph G with n vertices, the treewidth of G plus the treewidth of the complement of G is at least n−2. This bound is tight.
The visibility graph of a finite set of points in the plane has the points as vertices and an edge between two vertices if the line segment between them contains no other points. This paper establishes bounds on the edge- and vertex-connectivity of visibility graphs. Unless all its vertices are collinear, a visibility graph has diameter at most 2, and so it follows by a result of Plesník (1975) that its edge-connectivity equals its minimum degree. We strengthen the result of Plesník by showing that for any two vertices v and w in a graph of diameter 2, if deg(v) <= deg(w) then there exist deg(v) edge-disjoint vw-paths of length at most 4. Furthermore, we find that in visibility graphs every minimum edge cut is the set of edges incident to a vertex of minimum degree. For vertex-connectivity, we prove that every visibility graph with n vertices and at most l collinear vertices has connectivity at least (n-1)/(l-1), which is tight. We also prove the qualitatively stronger result that the vertex-connectivity is at least half the minimum degree. Finally, in the case that l=4 we improve this bound to two thirds of the minimum degree.
Miller and Muller (1960) and independently Moon and Moser (1965) determined the maximum number of maximal independent sets in an n-vertex graph. We give a new and simple proof of this result.
Robertson and Seymour proved that every graph with sufficiently large treewidth contains a large grid minor. However, the best known bound on the treewidth that forces an ℓ×ℓ grid minor is exponential in ℓ. It is unknown whether polynomial treewidth suffices. We prove a result in this direction. A \emph{grid-like-minor of order} ℓ in a graph G is a set of paths in G whose intersection graph is bipartite and contains a Kℓ-minor. For example, the rows and columns of the ℓ×ℓ grid are a grid-like-minor of order ℓ+1. We prove that polynomial treewidth forces a large grid-like-minor. In particular, every graph with treewidth at least cℓ4logℓ has a grid-like-minor of order ℓ. As an application of this result, we prove that the cartesian product G□K2 contains a Kℓ-minor whenever G has treewidth at least cℓ4logℓ.
Let a,b,c,d be four vertices in a graph G. A \emph{K4-minor rooted} at a,b,c,d consists of four pairwise-disjoint pairwise-adjacent connected subgraphs of G, respectively containing a,b,c,d. We characterise precisely when G contains a K4-minor rooted at a,b,c,d by describing six classes of obstructions, which are the edge-maximal graphs containing no K4-minor rooted at a,b,c,d. The following two special cases illustrate the full characterisation: (1) A 4-connected non-planar graph contains a K4-minor rooted at a,b,c,d for every choice of a,b,c,d. (2) A 3-connected planar graph contains a K4-minor rooted at a,b,c,d if and only if a,b,c,d are not on a single face.
Let P be a set of n points in general and convex position in the plane. Let Dn be the graph whose vertex set is the set of all line segments with endpoints in P, where disjoint segments are adjacent. The chromatic number of this graph was first studied by Araujo et al. [\emph{CGTA}, 2005]. The previous best bounds are 43n≤χ(Dn)<n−2n (ignoring lower order terms). In this paper we improve the lower bound to χ(Dn)≥n−2n, to conclude a near-tight bound on χ(Dn).
This paper studies the following question: Given a surface Σ and an integer n, what is the maximum number of cliques in an n-vertex graph embeddable in Σ? We characterise the extremal graphs for this question, and prove that the answer is between 8(n−ω)+2ω and 8n+3/22ω+o(2ω), where ω is the maximum integer such that the complete graph Kω embeds in Σ. For the surfaces S0, S1, S2, N1, N2, N3 and N4 we establish an exact answer.
The following theorem is proved: For all k-connected graphs G and H each with at least n vertices, the treewidth of the cartesian product of G and H is at least k(n−2k+2)−1. For n≫k this lower bound is asymptotically tight for particular graphs G and H. This theorem generalises a well known result about the treewidth of planar grid graphs.
This paper studies problems related to visibility among points in the plane. A point x \emph{blocks} two points v and w if x is in the interior of the line segment vwˉ. A set of points P is \emph{k-blocked} if each point in P is assigned one of k colours, such that distinct points v,w∈P are assigned the same colour if and only if some other point in P blocks v and w. The focus of this paper is the conjecture that each k-blocked set has bounded size (as a function of k). Results in the literature imply that every 2-blocked set has at most 3 points, and every 3-blocked set has at most 6 points. We prove that every 4-blocked set has at most 12 points, and that this bound is tight. In fact, we characterise all sets {n1,n2,n3,n4} such that some 4-blocked set has exactly ni points in the i-th colour class. Amongst other results, for infinitely many values of k, we construct k-blocked sets with k1.79... points.
We prove upper and lower bounds on the chromatic number of the square of the cartesian product of trees. The bounds are equal if each tree has even maximum degree.
A triangulation of a surface is \emph{irreducible} if there is no edge whose contraction produces another triangulation of the surface. We prove that every irreducible triangulation of a surface with Euler genus g≥1 has at most 13g−4 vertices. The best previous bound was 171g−72.
This paper addresses the following questions for a given tree T and integer d≥2: (1) What is the minimum number of degree-d subtrees that partition E(T)? (2) What is the minimum number of degree-d subtrees that cover E(T)? We answer the first question by providing an explicit formula for the minimum number of subtrees, and we describe a linear time algorithm that finds the corresponding partition. For the second question, we present a polynomial time algorithm that computes a minimum covering. We then establish a tight bound on the number of subtrees in coverings of trees with given maximum degree and pathwidth. Our results show that pathwidth is the right parameter to consider when studying coverings of trees by degree-3 subtrees. We briefly consider coverings of general graphs by connected subgraphs of bounded degree.
A drawing of a given (abstract) tree that is a minimum spanning tree of the vertex set is considered aesthetically pleasing. However, such a drawing can only exist if the tree has maximum degree at most 6. What can be said for trees of higher degree? We approach this question by supposing that a partition or covering of the tree by subtrees of bounded degree is given. Then we show that if the partition or covering satisfies some natural properties, then there is a drawing of the entire tree such that each of the given subtrees is drawn as a minimum spanning tree of its vertex set.
The big-line-big-clique conjecture states that for all k,ℓ≥2 there is an integer n such that every finite set of at least n points in the plane contains ℓ collinear points or k pairwise visible points. We show that this conjecture is false for infinite point sets, by constructing a countably infinite point set with no 4 collinear points and no 3 pairwise visible points.
Thomassen (1994) proved that every planar graph is 5-choosable. This result was generalised by {Š}krekovski (1998) and He et al. (2008), who proved that every K5-minor-free graph is 5-choosable. Both proofs rely on the characterisation of K5-minor-free graphs due to Wagner (1937). This paper proves the same result without using Wagner's structure theorem or even planar embeddings. Given that there is no structure theorem for graphs with no K6-minor, we argue that this proof suggests a possible approach for attacking the Hadwiger Conjecture.
Classes with bounded expansion, which generalise classes that exclude a topological minor, have recently been introduced by Nešetřil and Ossona de Mendez. These classes are defined by the fact that the maximum average degree of a shallow minor of a graph in the class is bounded by a function of the depth of the shallow minor. Several linear-time algorithms are known for bounded expansion classes (such as subgraph isomorphism testing), and they allow restricted homomorphism dualities, amongst other desirable properties. In this paper we establish two new characterisations of bounded expansion classes, one in terms of so-called topological parameters, the other in terms of controlling dense parts. The latter characterisation is then used to show that the notion of bounded expansion is compatible with Erdös-Rényi model of random graphs with constant average degree. In particular, we prove that for every fixed d>0, there exists a class with bounded expansion, such that a random graph of order n and edge probability d/n asymptotically almost surely belongs to the class. We then present several new examples of classes with bounded expansion that do not exclude some topological minor, and appear naturally in the context of graph drawing or graph colouring. In particular, we prove that the following classes have bounded expansion: graphs that can be drawn in the plane with a bounded number of crossings per edge, graphs with bounded stack number, graphs with bounded queue number, and graphs with bounded non-repetitive chromatic number. We also prove that graphs with `linear' crossing number are contained in a topologically-closed class, while graphs with bounded crossing number are contained in a minor-closed class.
We prove the following generalised empty pentagon theorem: for every integer ℓ≥2, every sufficiently large set of points in the plane contains ℓ collinear points or an empty pentagon. As an application, we settle the next open case of the "big line or big clique" conjecture of Kára, Pór, and Wood [\emph{Discrete Comput. Geom.} 34(3):497--506, 2005].
Every k-tree has book thickness at most k+1, and this bound is best possible for all k≥3. Vandenbussche et al. (2009) proved that every k-tree that has a smooth degree-3 tree decomposition with width k has book thickness at most k. We prove this result is best possible for k≥4, by constructing a k-tree with book thickness k+1 that has a smooth degree-4 tree decomposition with width k. This solves an open problem of Vandenbussche et al. (2009)
This expository paper discusses some conjectures related to visibility and blockers for sets of points in the plane.
For a graph G and integer k≥1, we define the token graph Fk(G) to be the graph with vertex set all k-subsets of V(G), where two vertices are adjacent in Fk(G) whenever their symmetric difference is a pair of adjacent vertices in G. Thus vertices of Fk(G) correspond to configurations of k indistinguishable tokens placed at distinct vertices of G, where two configurations are adjacent whenever one configuration can be reached from the other by moving one token along an edge from its current position to an unoccupied vertex. This paper introduces token graphs and studies some of their properties including: connectivity, diameter, cliques, chromatic number, Hamiltonian paths, and Cartesian products of token graphs.
Let F be a family of connected bipartite graphs, each with at least three vertices. A proper vertex colouring of a graph G with no bichromatic subgraph in F is $\F$-free. The F-free chromatic number χ(G,F) of a graph G is the minimum number of colours in an F-free colouring of G. For appropriate choices of F, several well-known types of colourings fit into this framework, including acyclic colourings, star colourings, and distance-2 colourings. This paper studies F-free colourings of the cartesian product of graphs. Let H be the cartesian product of the graphs G1,G2,...,Gd. Our main result establishes an upper bound on the F-free chromatic number of H in terms of the maximum F-free chromatic number of the Gi and the following number-theoretic concept. A set S of natural numbers is k-multiplicative Sidon if ax=by implies a=b and x=y whenever x,y∈S and 1≤a,b≤k. Suppose that χ(Gi,F)≤k and S is a k-multiplicative Sidon set of cardinality d. We prove that χ(H,F)≤1+2k⋅maxS. We then prove that the maximum density of a k-multiplicative Sidon set is Θ(1/logk). It follows that χ(H,F)≤O(dklogk). We illustrate the method with numerous examples, some of which generalise or improve upon existing results in the literature.
Consider the following relaxation of the Hadwiger Conjecture: For each t there exists Nt such that every graph with no Kt-minor admits a vertex partition into $\ceil{αt+β}$ parts, such that each component of the subgraph induced by each part has at most Nt vertices. The Hadwiger Conjecture corresponds to the case α=1, β=−1 and Nt=1. Kawarabayashi and Mohar [\emph{J. Combin. Theory Ser. B}, 2007] proved this relaxation with α=31/2 and β=0 (and Nt a huge function of t). This paper proves this relaxation with α=7/2 and β=−3/2. The main ingredients in the proof are: (1) a list colouring argument due to Kawarabayashi and Mohar, (2) a recent result of Norine and Thomas that says that every sufficiently large (t+1)-connected graph contains a Kt-minor, and (3) a new sufficient condition for a graph to have a set of edges whose contraction increases the connectivity.
Let Dk be the class of graphs for which every minor has minimum degree at most k. Then Dk is closed under taking minors. By the Robertson-Seymour graph minor theorem, Dk is characterised by a finite family of minor-minimal forbidden graphs, which we denote by Dk. This paper discusses Dk and related topics. We obtain four main results: We prove that every (k+1)-regular graph with less than 4/3(k+2) vertices is in Dk, and this bound is best possible. We characterise the graphs in Dk+1 that can be obtained from a graph in Dk by adding one new vertex. For k≤3 every graph in Dk is (k+1)-connected, but for large k, we exhibit graphs in Dk with connectivity 1. In fact, we construct graphs in Dk with arbitrary block structure. We characterise the complete multipartite graphs in Dk, and prove analogous characterisations with minimum degree replaced by connectivity, treewidth, or pathwidth.
To untangle a geometric graph means to move some of the vertices so that the resulting geometric graph has no crossings. Pach and Tardos [Discrete Comput. Geom., 2002] asked if every n-vertex geometric planar graph can be untangled while keeping at least n^εvertices fixed. We answer this question in the affirmative with ε=1/4. The previous best known bound was Ω((\log n / \log\log n)^{1/2}). We also consider untangling geometric trees. It is known that every n-vertex geometric tree can be untangled while keeping at least (n/3)^{1/2} vertices fixed, while the best upper bound was O(n\log n)^{2/3}. We answer a question of Spillner and Wolff [arXiv:0709.0170 2007] by closing this gap for untangling trees. In particular, we show that for infinitely many values of n, there is an n-vertex geometric tree that cannot be untangled while keeping more than 3(n^{1/2}-1) vertices fixed. Moreover, we improve the lower bound to (n/2)^{1/2}.
A set of vertices S \emph{resolves} a connected graph G if every vertex is uniquely determined by its vector of distances to the vertices in S. The \emph{metric dimension} of G is the minimum cardinality of a resolving set of G. Let Gβ,D be the set of graphs with metric dimension β and diameter D. It is well-known that the minimum order of a graph in Gβ,D is exactly β+D. The first contribution of this paper is to characterise the graphs in Gβ,D with order β+D for all values of β and D. Such a characterisation was previously only known for D≤2 or β≤1. The second contribution is to determine the maximum order of a graph in Gβ,D for all values of D and β. Only a weak upper bound was previously known.
A \emph{clique} is a set of pairwise adjacent vertices in a graph. We determine the maximum number of cliques in a graph for the following graph classes: (1) graphs with n vertices and m edges; (2) graphs with n vertices, m edges, and maximum degree Δ; (3) d-degenerate graphs with n vertices and m edges; (4) planar graphs with n vertices and m edges; and (5) graphs with n vertices and no K5-minor or no K3,3-minor. For example, the maximum number of cliques in a planar graph with n vertices is 8(n−2).
A graph G is a 2-tree if G=K_3, or G has a vertex v of degree 2, whose neighbours are adjacent, and Gǐs a 2-tree. A characterization of the degree sequences of 2-trees is given. This characterization yields a linear-time algorithm for recognizing and realizing degree sequences of 2-trees.
Let G be a graph with n vertices, with independence number α, and with with no Kt+1-minor for some t≥5. It is proved that (2α−1)(2t−5)≥2n−5.
Characterisations of interval graphs, comparability graphs, co-comparability graphs, permutation graphs, and split graphs in terms of linear orderings of the vertex set are presented. As an application, it is proved that interval graphs, co-comparability graphs, AT-free graphs, and split graphs have bandwidth bounded by their maximum degree.
A \emph{queue layout} of a graph consists of a total order of the vertices, and a partition of the edges into \emph{queues}, such that no two edges in the same queue are nested. The minimum number of queues in a queue layout of a graph is its \emph{queue-number}. A \emph{three-dimensional (straight-line grid) drawing} of a graph represents the vertices by points in Z3 and the edges by non-crossing line-segments. This paper contributes three main results: (1) It is proved that the minimum volume of a certain type of three-dimensional drawing of a graph G is closely related to the queue-number of G. In particular, if G is an n-vertex member of a proper minor-closed family of graphs (such as a planar graph), then G has a O(1)×O(1)×O(n) drawing if and only if G has O(1) queue-number. (2) It is proved that queue-number is bounded by tree-width, thus resolving an open problem due to Ganley and Heath (2001), and disproving a conjecture of Pemmaraju (1992). This result provides renewed hope for the positive resolution of a number of open problems in the theory of queue layouts. (3) It is proved that graphs of bounded tree-width have three-dimensional drawings with O(n) volume. This is the most general family of graphs known to admit three-dimensional drawings with O(n) volume. The proofs depend upon our results regarding \emph{track layouts} and \emph{tree-partitions} of graphs, which may be of independent interest.
A \emph{(k,t)-track layout} of a graph G consists of a (proper) vertex t-colouring of G, a total order of each vertex colour class, and a (non-proper) edge k-colouring such that between each pair of colour classes no two monochromatic edges cross. This structure has recently arisen in the study of three-dimensional graph drawings. This paper presents the beginnings of a theory of track layouts. First we determine the maximum number of edges in a (k,t)-track layout, and show how to colour the edges given fixed linear orderings of the vertex colour classes. We then describe methods for the manipulation of track layouts. For example, we show how to decrease the number of edge colours in a track layout at the expense of increasing the number of tracks, and vice versa. We then study the relationship between track layouts and other models of graph layout, namely stack and queue layouts, and geometric thickness. One of our principle results is that the queue-number and track-number of a graph are tied, in the sense that one is bounded by a function of the other. As corollaries we prove that acyclic chromatic number is bounded by both queue-number and stack-number. Finally we consider track layouts of planar graphs. While it is an open problem whether planar graphs have bounded track-number, we prove bounds on the track-number of outerplanar graphs, and give the best known lower bound on the track-number of planar graphs.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.