Search

A queue layout of a graph consists of a linear order of its vertices and a partition of its edges into queues, so that no two independent edges of the same queue are nested. The queue number of a graph is the minimum number of queues required by any of its queue layouts. A long-standing conjecture by Heath, Leighton and Rosenberg [SIAM J. Discrete Math., 5 (1992), pp. 398--412] states that the queue number of planar graphs is bounded. This conjecture has been partially settled in the positive for several subfamilies of planar graphs (most of which have bounded treewidth). In this paper, we make a further important step towards settling this conjecture. We prove that planar graphs of bounded degree (which may have unbounded treewidth) have bounded queue number. A notable implication of this result is that every planar graph of bounded degree admits a three-dimensional straight-line grid drawing in linear volume. Further implications are that every planar graph of bounded degree has bounded track number, and that every k-planar graph (i.e., every graph that can be drawn in the plane with at most k crossings per edge) of bounded degree has bounded queue number. [ABSTRACT FROM AUTHOR]

A graph G is called (2,k)‐connected if G is 2k‐edge‐connected and G−v is k‐edge‐connected for every vertex v. The study of (2,2)‐connected graphs is motivated by a theorem of Thomassen [J. Combin. Theory Ser. A 110 (2015), pp. 67–78] (that was a conjecture of Frank [SIAM J. Discrete Math. 5 (1992), no. 1, pp. 25–53]), which states that a graph has a 2‐vertex‐connected orientation if and only if it is (2,2)‐connected. In this paper, we provide a construction of the family of (2,k)‐connected graphs for k even, which generalizes the construction given by Jordán [J. Graph Theory 52 (2006), pp. 217–229] for (2,2)‐connected graphs. We also solve the corresponding connectivity augmentation problem: given a graph G and an integer k≥2, what is the minimum number of edges to be added to make G(2,k)‐connected. Both these results are based on a new splitting‐off theorem for (2,k)‐connected graphs. [ABSTRACT FROM AUTHOR]

A variety of powerful extremal results have been shown for the chromatic number of triangle-free graphs. Three noteworthy bounds are in terms of the number of vertices, edges, and maximum degree given by Poljak and Tuza [SIAM J. Discrete Math., 7 (1994), pp. 307--313] and Johansson. There have been comparatively fewer works extending these types of bounds to graphs with a small number of triangles. One noteworthy exception is a result of Alon, Krivelevich, and Sudakov [J. Combin. Theory Ser. B, 77 (1999), pp. 73--82] bounding the chromatic number for graphs with low degree and few triangles per vertex; this bound is nearly the same as for triangle-free graphs. This type of parametrization is much less rigid and has appeared in dozens of combinatorial constructions. In this paper, we show a similar type of result for X (G) as a function of the number of vertices n, the number of edges m, as well as the triangle count (both local and global measures). Our results smoothly interpolate between the generic bounds true for all graphs and bounds for triangle-free graphs. Our results are tight for most of these cases; we show how an open problem regarding fractional chromatic number and degeneracy in triangle-free graphs can resolve the small remaining gap in our bounds. [ABSTRACT FROM AUTHOR]

For integers k ≥1 and m ≥2, let g(k,m) be the least integer n ≥1 such that every graph with chromatic number at least n contains a (k + 1)-connected subgraph with chromatic number at least m. Refining the recent result of Gir\~ao and Narayanan [Bull. Lond. Math. Soc., 54 (2022), pp. 868--875] that g(k 1, k) ≤ 7k + 1 for all k≥ 2, we prove that g(k,m) ≤ max(m + 2k 2, (3 + 1/16)k≤) for all k ≥ 1 and m≥2. This sharpens earlier results of Alon et al. [J. Graph Theory, 11 (1987), pp. 367-371], of Chudnovsky [J. Combin. Theory Ser. B, 103 (2013), pp. 567-586], and of Penev, Thomass'e, and Trotignon [SIAM J. Discrete Math., 30 (2016), pp. 592--619]. Our result implies that g(k, k + 1) (3 + 1/16)k for all k \geq 1, making a step closer towards a conjecture of Thomassen [J. Graph Theory, 7 (1983), pp. 261--271] that g(k, k +1)≤3k +1, which was originally a result with a false proof and was the starting point of this research area. [ABSTRACT FROM AUTHOR]

The separation dimension of a graph G is the minimum positive integer d for which there is an embedding of G into ℝd, such that every pair of disjoint edges are separated by some axis-parallel hyperplane. We prove a conjecture of Alon et al. [SIAM J. Discrete Math. 2015] by showing that every graph with maximum degree Δ has separation dimension less than 20Δ, which is best possible up to a constant factor. We also prove that graphs with separation dimension 3 have bounded average degree and bounded chromatic number, partially resolving an open problem by Alon et al. [J. Graph Theory 2018]. [ABSTRACT FROM AUTHOR]