The square of every subcubic planar graph without 4-cycles and 5-cycles is 7-choosable

Ligang Jin, Yingli Kang, Seog-Jin Kim · 2025

Read The square of every subcubic planar graph without 4-cycles and 5-cycles is 7-choosable by Ligang Jin, Yingli Kang, Seog-Jin Kim (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-2507-00426.txt.

Introduction

Ligang Jin, Yingli Kang, and Seog-Jin Kim prove a coloring result in a 2025 mathematics paper. The square of a graph links every pair of points within two steps, and coloring it means assigning colors so linked points differ. For flat networks where each point has at most three links, seven colors suffice for the square.

The stronger question is list coloring, where each point picks from its own list of seven colors. Past work settled it for networks with no short cycles at all. This paper settles it when only four- and five-cycles are banned, widening the known safe zone. Such results ground frequency assignment in wireless networks.

Catalog record

CREATORLigang Jin, Yingli Kang, Seog-Jin Kim
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE22 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-00426

Browse the full library · About the Tower of Babel

Full text

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

The square of every subcubic planar graph without 4-cycles and 5-cycles is 7-choosable Ligang Jin, Yingli Kang, Seog-Jin Kim Abstract The square of a graph G G , denoted by G 2 G^{2} , has the same vertex set as G G and has an edge between two vertices if the distance between them in G G is at most 2 2 . Thomassen (2018) and independently, Hartke, Jahanbekam and Thomas (2016) proved that χ ⁡ ( G 2 ) ≤ 7 \chi(G^{2})\leq 7 if G G is a subcubic planar graph. A natural question is whether χ ℓ ​ ( G 2 ) ≤ 7 \chi_{\ell}(G^{2})\leq 7 or not if G G is a subcubic planar graph. Recently, Kim and Lian (2024) proved that χ ℓ ​ ( G 2 ) ≤ 7 \chi_{\ell}(G^{2})\leq 7 if G G is a subcubic planar graph of girth at least 6. In this paper, we prove that χ ℓ ​ ( G 2 ) ≤ 7 \chi_{\ell}(G^{2})\leq 7 if G G is a subcubic planar graph without 4-cycles and 5-cycles, which improves the result of Kim and Lian. Key words: List chromatic number; square of graph; subcubic planar graph; girth 1 Introduction The square of a graph G , denoted by G^{2} , has the same vertex set as G and has an edge between two vertices if the distance between them in G is at most 2 . We say that a graph G is subcubic if \Delta(G)\leq 3 , where \Delta(G) is the maximum degree in G . The girth of a graph G , denoted by g(G) , is the size of the smallest cycle in G . A cycle of length k is called a k -cycle . Let \chi(G) denote the chromatic number of a graph G . Given a graph G , finding the chromatic number of the square of G , \chi(G^{2}) , is a main research topic in the study of colorings of the square of graphs. On coloring squares of graphs, one of the most famous problems is Wegner’s conjecture, which states as follows. Conjecture 1 ( [ 15 ] ) . Let G be a planar graph. The chromatic number \chi(G^{2}) of G^{2} is at most 7 if \Delta(G)=3 , at most \Delta(G)+5 if 4\leq\Delta(G)\leq 7 , and at most \lfloor\frac{3\Delta(G)}{2}\rfloor if \Delta(G)\geq 8 . Conjecture 1 has received a lot of attention, but it is still widely open. The only case for which we know tight bound is when \Delta(G)=3 . Thomassen [ 14 ] showed that \chi(G^{2})\leq 7 if G is a planar graph with \Delta(G)=3 , that is, Conjecture 1 is true for \Delta(G)=3 . Conjecture 1 for \Delta(G)=3 was also confirmed by Hartke, Jahanbekam and Thomas [ 7 ] with extensive computer case-checking. With conditions on \Delta(G) , several upper bounds of \chi(G^{2}) were obtained. Bousquet, Deschamps, Meyer and Pierron [ 3 ] showed that \chi(G^{2})\leq 12 if G is a planar graph with \Delta(G)\leq 4 . For \Delta(G)\leq 5 , recently the upper bounds on \chi(G^{2}) were improved in [ 1 , 6 , 16 ] , and now the best known upper bound was obtained in [ 6 ] . Deniz [ 6 ] showed that \chi(G^{2})\leq 16 if G is a planar graph with \Delta(G)\leq 5 . Moreover, Bousquet, Deschamps, Meyer and Pierron [ 2 ] showed that \chi(G^{2})\leq 2\Delta(G)+7 if G is a planar graph with 6\leq\Delta(G)\leq 31 . The best known upper bound for general \Delta(G) is that \chi(G^{2})\leq\lceil\frac{5\Delta(G)}{3}\rceil+78 by Molloy and Salavatipour [ 13 ] . On the other hand, Havet, van den Heuvel, McDiarmid, and Reed [ 9 ] proved that Conjecture 1 holds asymptotically. One may see a detailed story on the study of Wegner’s conjecture in [ 4 ] . A list assignment for a graph is a function L that assigns to each vertex a list of available colors. A graph is L -colorable if it has a proper coloring f such that f(v)\in L(v) for all vertices v . A graph is called k -choosable if it is L -colorable whenever all lists of L have size k . The list chromatic number \chi_{\ell}(G) is the minimum k such that G is k -choosable. Since it was known in [ 14 ] that \chi(G^{2})\leq 7 if G is a subcubic planar graph, the following natural question was raised in [ 5 ] and [ 9 ] , independently. Question 2 ( [ 5 , 9 ] ) . Is it true that \chi_{\ell}(G^{2})\leq 7 if G is a subcubic planar graph? Question 2 was motivated by the List Square Coloring Conjecture which states that \chi_{\ell}(G^{2})=\chi(G^{2}) for every graph G . However, the List Square Coloring Conjecture was disproved in [ 12 ] . Note that a positive result for the List Square Coloring Conjecture for a special class of graphs is still interesting. It was conjectured in [ 9 ] that \chi_{\ell}(G^{2})=\chi(G^{2}) if G is a planar graph. But, recently Hasanvand [ 8 ] proved that there exists a cubic claw-free planar graph G such that \chi(G^{2})=4<\chi_{\ell}(G^{2}) . So, it would be interesting to answer Question 2 . But, considering the result of Thomassen in [ 14 ] , it would be not easy to answer Question 2 completely if it is true. One natural approach to Question 2 is to forbid cycles of certain lengths. For general upper bound on \chi_{\ell}(G^{2}) for a subcubic graph G , Cranston and Kim [ 5 ] proved that \chi_{\ell}(G^{2})\leq 8 if G is a connected graph (not necessarily planar) with \Delta(G)=3 and if G is not the Petersen graph. Cranston and Kim [ 5 ] also proved that \chi_{\ell}(G^{2})\leq 7 if G is a subcubic planar graph with g(G)\geq 7 . Recently, Kim and Lian [ 11 ] made an interesting progress by showing the following result. Theorem 3 ( [ 11 ] ) . If G is a subcubic planar graph with girth at least 6, then \chi_{\ell}(G^{2})\leq 7 . In this paper, we consider subcubic planar graphs that have no 4-cycles and 5-cycles, and we improve Theorem 3 by showing the following main theorem. Theorem 4 . If G is a subcubic planar graph without 4-cycles and 5-cycles, then \chi_{\ell}(G^{2})\leq 7 . In Section 2 , we will prove several reducible configurations and prove Theorem 4 . 2 Proof of Theorem 4 In this section, let G be a minimal counterexample to Theorem 4 . It means that for any proper subgraph H of G , \chi_{\ell}(H^{2})\leq 7 , but \chi_{\ell}(G^{2})>7 . Let L be a list assignment of G of size 7 such that G^{2} is not L -colorable. For a vertex x , d_{G}(x) is the degree of x in G . A vertex of degree k is called a k -vertex . For vertices x and y in G , d_{G}(x,y) is the distance between x and y in G . First, we state some basic properties of G , which were stated in previous papers and can be proved similarly as in [ 11 ] . Lemma 5 . G satisfies the following properties. (a) G has no 1-vertex. (Lemma 8 in [

Read the complete text