Planar graphs without cycles of length 4 or 5 are ( 7 ​ m : 2 ​ m ) (7m:2m) -DP-colorable

Xiaoyan Xu Xuding Zhu School of Mathematical Sciences, Zhejiang Normal University · 2025

Read Planar graphs without cycles of length 4 or 5 are ( 7 ​ m : 2 ​ m ) (7m:2m) -DP-colorable by Xiaoyan Xu Xuding Zhu School of Mathematical Sciences, Zhejiang Normal University (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-12914.txt.

Introduction

Xiaoyan Xu and Xuding Zhu prove a coloring theorem for planar graphs with no cycles of length four or five. Steinberg conjectured in 1976 that all such graphs are three-colorable; the claim drew decades of work before being refuted in 2017. Interest then shifted to stronger notions, such as multiple colorings and list colorings, where each vertex must receive several colors from its own allowed list. Earlier results gave progressively better ratios for this family of graphs, while other work showed limits on plain choosability.

Xu and Zhu prove that for every positive integer m, these graphs are DP-colorable in the ratio seven m to two m, which settles the list coloring statement. DP-coloring generalizes list coloring, so the theorem is correspondingly strong. The paper closes one line of the post-Steinberg program.

Catalog record

CREATORXiaoyan Xu Xuding Zhu School of Mathematical Sciences, Zhejiang Normal University
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-12914

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Planar graphs without cycles of length 4 or 5 are ( 7 ​ m : 2 ​ m ) (7m:2m) -DP-colorable Xiaoyan Xu Xuding Zhu School of Mathematical Sciences, Zhejiang Normal University Abstract It was conjectured by Steinberg in 1976 that planar graphs without cycles of length 4 or 5 are 3-colorable. This conjecture attracted a substantial amount of attention and was finally refuted by Cohen-Addad, Hebdige, Král’, Li and Salgado in 2017. Although Steinberg’s conjecture is settled, coloring of this family of graphs, as well as some other families of planar graphs forbidding certain cycle lengths have been attracting a lot of recent attention and many challenging problems remain open. One problem of interest is multiple coloring and multiple list coloring of this family of graphs. It was proved by Dvǒrák and Hu that planar graphs without cycles of length 4 or 5 are ( 11 , 3 ) (11,3) -colorable, and this result was improved by Wang, who proved that graphs in this family are ( 7 : 2 ) (7:2) -colorable. On the other hand, it was proved by Xu and Zhu that for every positive integer m m , there is a graph in this family which is not ( 3 ​ m + ⌊ m − 1 12 ⌋ , m ) (3m+\lfloor\frac{m-1}{12}\rfloor,m) -choosable. In this paper, we prove that for any positive integer m m , graphs in this family are ( 7 ​ m : 2 ​ m ) (7m:2m) -DP-colorable, and hence ( 7 ​ m , 2 ​ m ) (7m,2m) -choosable. 1 Introduction One problem of interest in planar graph coloring is which planar graphs are 3-colorable, and which planar graphs are 3-choosable. For a sequence k_{1},k_{2},\ldots,k_{q} of positive integers, we denote by \mathcal{P}_{k_{1},k_{2},\ldots,k_{q}} the family of connected planar graphs without cycles of length k_{i} for i=1,2,\ldots,q . The classical Grötzsch Theorem [ 10 ] asserts graphs in \mathcal{P}_{3} are 3-colorable. In 1976, Steinberg conjectured that graphs in \mathcal{P}_{4,5} are 3-colorable (see [ 6 ] ). This conjecture attracted considerable attention. As an approach to this conjecture, Erdős proposed the problem in 1991 to determine the smallest integer k such that every graph in \mathcal{P}_{4,5,\ldots,k} is 3-colorable. It was proved by Abbott and Zhou that k\leq 11 [ 1 ] , and this bound was improved by Sanders and Zhao to k\leq 9 [ 12 ] , and further improved by Borodin, Glebov, Raspaud and Salavatipour to k\leq 7 [ 5 ] . Many other relaxations or variations of Steinberg’s conjecture have been proved in the literature. For example, it is known that for 4<i<j<10 and (i,j)\notin\{(5,6),(7,8),(5,9),(8,9)\} , graphs in \mathcal{P}_{4,i,j} are 3-colorable (see [ 11 ] for detailed references). In 2017, Cohen-Addad, Hebdige, Král’, Li and Salgado [ 7 ] proved that Steinberg’s conjecture is false. Now it remains a challenging open question whether graphs in \mathcal{P}_{4,5,6} are 3-colorable. For list coloring, Thomassen’s classical result asserts that planar graphs of girth at least 5 are 3-choosable. Erdős’ problem is also naturally extended to the list version: Determine the smallest integer \ell such that graphs in \mathcal{P}_{4,5,\ldots,\ell} are 3-choosable. It was proved by Voigt [ 13 ] that \ell\geq 6 , and proved by Dvǒrák and Postle [ 9 ] that \ell\leq 8 . Moreover, it is known that graphs in \mathcal{P}_{4,7,9},\mathcal{P}_{3,6,7,8},\mathcal{P}_{4,5,6,9},\mathcal{P}_{4,6,8,9} are 3-DP-colorable, and hence 3 -choosable (see [ 11 ] for detailed references). Multiple coloring and multiple list coloring of graphs allow us to explore the colorability of graphs in a finer scale. As Steinberg’s conjecture is disproved, a natural problem is explore multiple coloring of graphs in \mathcal{P}_{4,5} . Definition 1 . Given a graph G and a function g\in\mathbb{N}^{G} , a g -fold coloring of G is a mapping \phi which assigns to each vertex v of G a set \phi(v) of g(v) colors, so that adjacent vertices receive disjoint color sets. For a mapping f:V(G)\to\mathbb{N} , an f -list assignment of G is a mapping L that assigns to each vertex v a set L(v) of f(v) colors. An (L,g) -coloring of G is a g -fold coloring \phi of G such that \phi(v)\subseteq L(v) for each vertex v . We say G is (f,g) -choosable if G has an (L,g) -coloring for each f -list assignment L . For positive integers a,b , we say G is (a,b) -choosable if G is (f,g) -choosable for the constant functions f(v)=a and g(v)=b for all v . If L(v)=[a]=\{1,2,\ldots,a\} for each vertex v , then an (L,b) -coloring of a graph G is called an (a,b) -coloring of G . The fractional chromatic number of G is defined as \chi_{f}(G)=\inf\{\frac{a}{b}:G\text{ is $(a,b)$-colorable}\}. The fractional choice number of G is defined as ch_{f}(G)=\inf\{\frac{a}{b}:G\text{ is $(a,b)$-choosable}\}. It was proved by Alon,Tuza and Voigt [ 2 ] that if G is (a,b) -colorable, then for some positive integer m , G is (am,bm) -choosable. Hence ch_{f}(G)=\chi_{f}(G) for all G . So ch_{f}(G) is not a new parameter. The concept of strong fractional choice number ch_{f}^{*}(G) of a graph G , introduced by Zhu in 2017 [ 16 ] , is defined as follows: ch_{f}^{*}(G)=\inf\{r:G\text{ is $(a,b)$-choosable for all integers $a,b$ with $a/b\geq r$}\}. For a family \mathcal{G} of graphs, let \chi_{f}(\mathcal{G})=\sup\{\chi_{f}(G):G\in\mathcal{G}\}\text{ and }ch_{f}^{*}(\mathcal{G})=\sup\{ch_{f}^{*}(G):G\in\mathcal{G}\}. Multiple coloring and multiple list coloring of graphs in \mathcal{P}_{4,5} are studied in a few papers. It was proved by Dvǒrák and Hu [ 8 ] that every graph G\in\mathcal{P}_{4,5} is (11,3) -colorable. This result was improved by Wang [ 14 ] who proved that every graph G\in\mathcal{P}_{4,5} is (7,2) -colorable. The current known upper bound for the strong fractional choice number is 4 , and for the lower bound, it was proved by Xu and Zhu [ 15 ] that for any positive integer m , there is a graph G\in\mathcal{P}_{4,5} which is not (3m+\lfloor\frac{m-1}{12}\rfloor,m) -choosable. This implies that ch_{f}^{*}(\mathcal{P}_{4,5})\geq 3+\frac{1}{12} . In this paper, we prove that for any positive integer m , every planar graph G\in\mathcal{P}_{4,5} is (7m,2m) -choosable, and hence ch_{f}^{*}(\mathcal{P}_{4,5})\leq 3+\frac{1}{2} . Our result is proved in the setting of multiple DP-coloring of graphs. The concept of DP-coloring (also known as correspondence coloring) is a generalization of list coloring introduced by Dvořák and Postle in [ 9 ] . Definition 2 . Let G be a graph. A cover of G is a pair (L,M) , where L=\left\{L(v):v\in V(G)\right\} is a family of pairwise disjoint sets, and M=\left\{M_{e}:e\in E(G)\right\} is a family of matchings such that for each edge e=uv , M_{e} is a matching between sets L(u) and L(v) . For a function f:V(G)\to\mathbb{N} , we say (L,M) is a f -cover of G if \left|L(v)\right|=f(v) for each vertex v\in V(G) . Definition 3 . Given a cover \mathcal{H}=(L,M) of a graph G , an \mathcal{H} -coloring of G is a mapping \phi:V(G)\to\cup_{v\in V(G)}L(v) such that for each vertex v\in V(G),\phi(v)\in L(v) , for each edge e=uv\in E(G),\phi(u)\phi(v)\neq E(M_{e}) . We say G is \mathcal{H} -colorable if it has an \mathcal{H} -coloring. For a function f:V(G)\to\mathbb{N} , we say G is f -DP-colorable if G is \mathcal{H} -colorable for every f -cover \mathcal{H} of G . The DP-chromatic number of G is defined as \chi_{DP}(G)=\min\{k:G\text{ is $k$-DP-colorable}\}. The concept of

Read the complete text