BZPEER

preprint2023arXiv

An Improved Bound for the Linear Arboricity Conjecture

In 1980, Akiyama, Exoo and Harary posited the Linear Arboricity Conjecture which states that any graph $G$ of maximum degree $Δ$ can be decomposed into at most $\left\lceil \fracΔ{2}\right\rceil$ linear forests. (A forest is linear if all of its components are paths.) In 1988, Alon proved the conjecture holds asymptotically. The current best bound is due to Ferber, Fox and Jain from 2020 who showed that $\fracΔ{2}+ O(Δ^{.661})$ suffices for large enough $Δ$ . Here, we show that $G$ admits a decomposition into at most $\fracΔ{2}+ 3\sqrtΔ \log^4 Δ$ linear forests provided $Δ$ is large enough. Moreover, our result also holds in the more general list setting, where edges have (possibly different) sets of permissible linear forests. Thus our bound also holds for the List Linear Arboricity Conjecture which was only recently shown to hold asymptotically by Kim and the second author. Indeed, our proof method ties together the Linear Arboricity Conjecture and the well-known List Colouring Conjecture; consequently, our error term for the Linear Arboricity Conjecture matches the best known error-term for the List Colouring Conjecture due to Molloy and Reed from 2000. This follows as we make two copies of every colour and then seek a proper edge colouring where we avoid bicoloured cycles between a colour and its copy; we achieve this via a clever modification of the nibble method.

preprint2022arXiv

An even better Density Increment Theorem and its application to Hadwiger's Conjecture

In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$ -colorable for every $t\ge 1$ . In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$ and hence is $O(t\sqrt{\log t})$ -colorable. Recently, Norin, Song and the author showed that every graph with no $K_t$ minor is $O(t(\log t)^β)$ -colorable for every $β> 1/4$ , making the first improvement on the order of magnitude of the $O(t\sqrt{\log t})$ bound. More recently, the author showed that every graph with no $K_t$ minor is $O(t (\log t)^β)$ -colorable for every $β> 0$ ; more specifically, they are $t \cdot 2^{ O((\log \log t)^{2/3}) }$ -colorable. In combination with that work, we show in this paper that every graph with no $K_t$ minor is $O(t (\log \log t)^{6})$ -colorable.

preprint2022arXiv

Further progress towards Hadwiger's conjecture

In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$ -colorable for every $t\ge 1$ . In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$ and hence is $O(t\sqrt{\log t})$ -colorable. Recently, Norin, Song and the author showed that every graph with no $K_t$ minor is $O(t(\log t)^β)$ -colorable for every $β> 1/4$ , making the first improvement on the order of magnitude of the $O(t\sqrt{\log t})$ bound. Building on that work, we show in this paper that every graph with no $K_t$ minor is $O(t (\log t)^β)$ -colorable for every $β> 0$ . More specifically in conjunction with another paper by the author, they are $O(t \cdot (\log \log t)^{18})$ -colorable.

preprint2022arXiv

Halfway to Hadwiger's Conjecture

In 1943, Hadwiger conjectured that every $K_t$ -minor-free graph is $(t-1)$ -colorable for every $t\ge 1$ . In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$ and hence is $O(t\sqrt{\log t})$ -colorable. Very recently, Norin and Song proved that every graph with no $K_t$ minor is $O(t(\log t)^{0.354})$ -colorable. Improving on the second part of their argument, we prove that every graph with no $K_t$ minor is $O(t(\log t)^β)$ -colorable for every $β> \frac{1}{4}$ .

preprint2021arXiv

Asymptotically good edge correspondence colouring

We prove that every simple graph with maximum degree $Δ$ has an edge correspondence colouring with $Δ+o(Δ)$ colours.

preprint2020arXiv

Breaking the degeneracy barrier for coloring graphs with no $K_t$ minor

In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$ -colorable for every $t\geq 1$ . In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$ and hence is $O(t\sqrt{\log t})$ -colorable. We show that every graph with no $K_t$ minor is $O(t(\log t)^β)$ -colorable for every $β> 1/4$ , making the first improvement on the order of magnitude of the Kostochka-Thomason bound.

preprint2020arXiv

Connectivity and choosability of graphs with no $K_t$ minor

In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$ -colorable for every $t\ge 1$ . While Hadwiger's conjecture does not hold for list-coloring, the linear weakening is conjectured to be true. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$ and thus is $O(t\sqrt{\log t})$ -list-colorable. Recently, the authors and Song proved that every graph with no $K_t$ minor is $O(t(\log t)^β)$ -colorable for every $β> \frac 1 4$ . Here, we build on that result to show that every graph with no $K_t$ minor is $O(t(\log t)^β)$ -list-colorable for every $β> \frac 1 4$ . Our main new tool is an upper bound on the number of vertices in highly connected $K_t$ -minor-free graphs: We prove that for every $β> \frac 1 4$ , every $Ω(t(\log t)^β)$ -connected graph with no $K_t$ minor has $O(t (\log t)^{7/4})$ vertices.

preprint2016arXiv

5-list-coloring planar graphs with distant precolored vertices

We answer positively the question of Albertson asking whether every planar graph can be $5$ -list-colored even if it contains precolored vertices, as long as they are sufficiently far apart from each other. In order to prove this claim, we also give bounds on the sizes of graphs critical with respect to 5-list coloring. In particular, if G is a planar graph, H is a connected subgraph of G and L is an assignment of lists of colors to the vertices of G such that |L(v)| >= 5 for every v in V(G)-V(H) and G is not L-colorable, then G contains a subgraph with O(|H|^2) vertices that is not L-colorable.

preprint2016arXiv

Bounded Diameter Arboricity

We introduce the notion of \emph{bounded diameter arboricity}. Specifically, the \emph{diameter- $d$ arboricity} of a graph is the minimum number $k$ such that the edges of the graph can be partitioned into $k$ forests each of whose components has diameter at most $d$ . A class of graphs has bounded diameter arboricity $k$ if there exists a natural number $d$ such that every graph in the class has diameter- $d$ arboricity at most $k$ . We conjecture that the class of graphs with arboricity at most $k$ has bounded diameter arboricity at most $k+1$ . We prove this conjecture for $k\in \{2,3\}$ by proving the stronger assertion that the union of a forest and a star forest can be partitioned into two forests of diameter at most 18. We use these results to characterize the bounded diameter arboricity for planar graphs of girth at least $g$ for all $g\ne 5$ . As an application we show that every 6-edge-connected planar (multi)graph contains two edge-disjoint $\frac{18}{19}$ -thin spanning trees.

preprint2016arXiv

Chromatic index determined by fractional chromatic index

Given a graph $G$ possibly with multiple edges but no loops, denote by $Δ$ the {\it maximum degree}, $μ$ the {\it multiplicity}, $χ'$ the {\it chromatic index} and $χ_f'$ the {\it fractional chromatic index} of $G$ , respectively. It is known that $Δ\le χ_f' \le χ' \le Δ+ μ$ , where the upper bound is a classic result of Vizing. While deciding the exact value of $χ'$ is a classic NP-complete problem, the computing of $χ_f'$ is in polynomial time. In fact, it is shown that if $χ_f' > Δ$ then $χ_f'= \max \frac{|E(H)|}{\lfloor |V(H)|/2\rfloor}$ , where the maximality is over all induced subgraphs $H$ of $G$ . Gupta\,(1967), Goldberg\,(1973), Andersen\,(1977), and Seymour\,(1979) conjectured that $χ'=\lceilχ_f'\rceil$ if $χ'\ge Δ+2$ , which is commonly referred as Goldberg's conjecture. In this paper, we show that if $χ' >Δ+\sqrt[3]{Δ/2}$ then $χ'=\lceilχ_f'\rceil$ . The previous best known result is for graphs with $χ'> Δ+\sqrt{Δ/2}$ obtained by Scheide, and by Chen, Yu and Zang, independently. It has been shown that Goldberg's conjecture is equivalent to the following conjecture of Jakobsen: {\it For any positive integer $m$ with $m\ge 3$ , every graph $G$ with $χ'>\frac{m}{m-1}Δ+\frac{m-3}{m-1}$ satisfies $χ'=\lceilχ_f'\rceil$ .} Jakobsen's conjecture has been verified for $m$ up to 15 by various researchers in the last four decades. We show that it is true for $m\le 23$ . Moreover, we show that Goldberg's conjecture holds for graphs $G$ with $Δ\leq 23$ or $|V(G)|\leq 23$ .

preprint2016arXiv

Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8

We introduce a new variant of graph coloring called correspondence coloring which generalizes list coloring and allows for reductions previously only possible for ordinary coloring. Using this tool, we prove that excluding cycles of lengths 4 to 8 is sufficient to guarantee 3-choosability of a planar graph, thus answering a question of Borodin.

preprint2016arXiv

Exponentially Many 4-List-Colorings of Triangle-Free Graphs on Surfaces

Thomassen proved that every planar graph $G$ on $n$ vertices has at least $2^{n/9}$ distinct $L$ -colorings if $L$ is a 5-list-assignment for $G$ and at least $2^{n/10000}$ distinct $L$ -colorings if $L$ is a 3-list-assignment for $G$ and $G$ has girth at least five. Postle and Thomas proved that if $G$ is a graph on $n$ vertices embedded on a surface $Σ$ of genus $g$ , then there exist constants $ε,c_g > 0$ such that if $G$ has an $L$ -coloring, then $G$ has at least $c_g2^{εn}$ distinct $L$ -colorings if $L$ is a 5-list-assignment for $G$ or if $L$ is a 3-list-assignment for $G$ and $G$ has girth at least five. More generally, they proved that there exist constants $ε,α>0$ such that if $G$ is a graph on $n$ vertices embedded in a surface $Σ$ of fixed genus $g$ , $H$ is a proper subgraph of $G$ , and $ϕ$ is an $L$ -coloring of $H$ that extends to an $L$ -coloring of $G$ , then $ϕ$ extends to at least $2^{ε(n - α(g + |V(H)|))}$ distinct $L$ -colorings of $G$ if $L$ is a 5-list-assignment or if $L$ is a 3-list-assignment and $G$ has girth at least five. We prove the same result if $G$ is triangle-free and $L$ is a 4-list-assignment of $G$ , where $ε=\frac{1}{8}$ , and $α= 130$ .

preprint2016arXiv

Five-list-coloring graphs on surfaces III. One list of size one and one list of size two

Let $G$ be a plane graph with outer cycle $C$ and let $(L(v):v\in V(G))$ be a family of non-empty sets. By an $L$ -coloring of $G$ we mean a (proper) coloring $ϕ$ of $G$ such that $ϕ(v)\in L(v)$ for every vertex $v$ of $G$ . Thomassen proved that if $v_1,v_2\in V(C)$ are adjacent, $L(v_1)\ne L(v_2)$ , $|L(v)|\ge3$ for every $v\in V(C)-\{v_1,v_2\}$ and $|L(v)|\ge5$ for every $v\in V(G)-V(C)$ , then $G$ has an $L$ -coloring. What happens when $v_1$ and $v_2$ are not adjacent? Then an $L$ -coloring need not exist, but in the first paper of this series we have shown that it exists if $|L(v_1)|,|L(v_2)|\ge2$ . Here we characterize when an $L$ -coloring exists if $|L(v_1)|\ge1$ and $|L(v_2)|\ge2$ . This result is a lemma toward a more general theorem along the same lines, which we will use to prove that minimally non- $L$ -colorable planar graphs with two precolored cycles of bounded length are of bounded size. The latter result has a number of applications which we pursue elsewhere.

preprint2016arXiv

Reconstruction of infinite matroids from their 3-connected minors

We show that any infinite matroid can be reconstructed from the torsos of a tree-decomposition over its 2-separations, together with local information at the ends of the tree. We show that if the matroid is tame then this local information is simply a choice of whether circuits are permitted to use that end. The same is true if each torso is planar, with all gluing elements on a common face.

preprint2015arXiv

The structure of 2-separations of infinite matroids

Generalizing a well known theorem for finite matroids, we prove that for every (infinite) connected matroid M there is a unique tree T such that the nodes of T correspond to minors of M that are either 3-connected or circuits or cocircuits, and the edges of T correspond to certain nested 2-separations of M. These decompositions are invariant under duality.

preprint2014arXiv

Characterizing 4-Critical Graphs of Ore-Degree at most Seven

Dirac introduced the notion of a k-critical graph, a graph that is not (k-1)-colorable but whose every proper subgraph is (k-1)-colorable. Brook's Theorem states that every graph with maximum degree k is k-colorable unless it contains a subgraph isomorphic to K_{k+1} (or an odd cycle for k=2). Equivalently, for all k>=4, the only k-critical graph of maximum degree k-1 is K_k. A natural generalization of Brook's theorem is to consider the Ore-degree of a graph, which is the maximum of d(u)+d(v) over all edges uv. Kierstead and Kostochka proved that for all k>=6 the only k-critical graph with Ore-degree at most 2k-1 is K_k. Kostochka, Rabern and Steibitz proved that the only 5-critical graphs with Ore-degree at most 9 are K_5 and a graph they called O_5. A different generalization of Brook's theorem, motivated by Hajos' construction, is Gallai's conjectured bound on the minimum density of a k-critical graph. Recently, Kostochka and Yancey proved Gallai's conjecture. Their proof for k>=5 implies the above results on Ore-degree. However, the case for k=4 remains open, which is the subject of this paper. Kostochka and Yancey's short but beautiful proof for the case k=4 says that if $G$ is a $4$ -critical graph, then |E(G)|>= (5|V(G)|-2)/3. We prove the following bound which is better when there exists a large independent set of degree three vertices: if G is a 4-critical graph G, then |E(G)|>= 1.6 |V(G)| + .2 alpha(D_3(G)) - .6, where D_3(G) is the graph induced by the degree three vertices of G. As a corollary, we characterize the 4-critical graphs with Ore-degree at most seven as precisely the graphs of Ore-degree seven in the family of graphs obtained from K_4 and Ore compositions.

preprint2014arXiv

Density of 5/2-critical graphs

A graph G is 5/2-critical if G has no circular 5/2-coloring (or equivalently, homomorphism to C_5), but every proper subgraph of G has one. We prove that every 5/2-critical graph on n>=4 vertices has at least (5n-2)/4 edges, and list all 5/2-critical graphs achieving this bound. This implies that every planar or projective-planar graph of girth at least 10 is 5/2-colorable.

preprint2014arXiv

On the Minimum Edge-Density of 4-Critical Graphs of Girth Five

We prove that if G is a 4-critical graph of girth at least five then |E(G)|>=(5|V(G)|+2)/3. As a corollary, graphs of girth at least five embeddable in the Klein bottle or torus are 3-colorable. These are results of Thomas and Walls, and Thomassen respectively. The proof uses the new potential technique developed by Kostochka and Yancey who proved that 4-critical graphs satisfy: |E(G)|>=(5|V(G)|-2)/3.

preprint2012arXiv

Five-coloring graphs on the Klein bottle

We exhibit an explicit list of nine graphs such that a graph drawn in the Klein bottle is 5-colorable if and only if it has no subgraph isomorphic to a member of the list.

preprint2011arXiv

Sub-exponentially many 3-colorings of triangle-free planar graphs

Thomassen conjectured that every triangle-free planar graph on n vertices has exponentially many 3-colorings, and proved that it has at least 2^[n^(1/12)/20000] distinct 3-colorings. We show that it has at least 2^sqrt(n/362) distinct 3-colorings.

Luke Postle

Research overview

Is this your work?

20 publications

An Improved Bound for the Linear Arboricity Conjecture

An even better Density Increment Theorem and its application to Hadwiger's Conjecture

Further progress towards Hadwiger's conjecture

Halfway to Hadwiger's Conjecture

Asymptotically good edge correspondence colouring

Breaking the degeneracy barrier for coloring graphs with no $K_t$ minor

Connectivity and choosability of graphs with no $K_t$ minor

5-list-coloring planar graphs with distant precolored vertices

Bounded Diameter Arboricity

Chromatic index determined by fractional chromatic index

Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8

Exponentially Many 4-List-Colorings of Triangle-Free Graphs on Surfaces

Five-list-coloring graphs on surfaces III. One list of size one and one list of size two

Reconstruction of infinite matroids from their 3-connected minors

The structure of 2-separations of infinite matroids

Characterizing 4-Critical Graphs of Ore-Degree at most Seven

Density of 5/2-critical graphs

On the Minimum Edge-Density of 4-Critical Graphs of Girth Five

Five-coloring graphs on the Klein bottle

Sub-exponentially many 3-colorings of triangle-free planar graphs

See the researcher in context

Building this map preview

Luke Postle

Research overview

Is this your work?

20 publications

An Improved Bound for the Linear Arboricity Conjecture

An even better Density Increment Theorem and its application to Hadwiger's Conjecture

Further progress towards Hadwiger's conjecture

Halfway to Hadwiger's Conjecture

Asymptotically good edge correspondence colouring

Breaking the degeneracy barrier for coloring graphs with no KtK_tKt​ minor

Connectivity and choosability of graphs with no KtK_tKt​ minor

5-list-coloring planar graphs with distant precolored vertices

Bounded Diameter Arboricity

Chromatic index determined by fractional chromatic index

Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8

Exponentially Many 4-List-Colorings of Triangle-Free Graphs on Surfaces

Five-list-coloring graphs on surfaces III. One list of size one and one list of size two

Reconstruction of infinite matroids from their 3-connected minors

The structure of 2-separations of infinite matroids

Characterizing 4-Critical Graphs of Ore-Degree at most Seven

Density of 5/2-critical graphs

On the Minimum Edge-Density of 4-Critical Graphs of Girth Five

Five-coloring graphs on the Klein bottle

Sub-exponentially many 3-colorings of triangle-free planar graphs

See the researcher in context

Building this map preview

Breaking the degeneracy barrier for coloring graphs with no $K_t$ minor

Connectivity and choosability of graphs with no $K_t$ minor