2022/11/01 by Morteza Hasanvand, Hasanvand, Morteza
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2211.00622
openalex publication_date 2022/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Kostochka and Woodall (2001) conjectured that the square of every graph has the same chromatic number and list chromatic number. In 2015 Kim and Park disproved this conjecture for non-bipartite and bipartite graphs. It was asked by several authors whether this conjecture holds for bipartite graphs with small degrees, claw-free graphs, or line graphs. In this paper, we introduce several kinds of counterexamples to this conjecture to solve three open problems posed by Kim and Park~(2015), Kim, Kwon, and Park~(2015), and Dai, Wang, Yang, and Yu~(2018). In particular, we disprove a planar version of this conjecture proposed by Havet, Heuvel, McDiarmid, and Reed (2017). This conjecture was originally proposed to make a stronger version of the List Total Coloring Conjecture. In order to make a revised version, it remains to decide whether this conjecture holds for bipartite graphs G by imposing a lower bound on the chromatic number of the square graph G2 in terms of its maximum degree as the condition χ(G2) ≥ (1)/(2) Δ(G2)+1 (or by adding an upper bound on the number of colors used in lists for a weaker version). To support this version, we will show that the bipartite condition cannot be dropped even by increasing the lower bound arbitrarily. Finally, we investigate non-choosable graphs with bounded maximum degree in bipartite or planar graphs. Consequently, we improve several graph constructions due to Erd\H os, Rubin, and Taylor~(1980), Bessy, Havet, and Palaysi (2002), Voigt (1993), Mirzakhani (1996), and Glebov, Kostochka, and Tashkinov (2005) in terms of maximum degree or order. In addition, we characterize edge-minimal 3-chromatic non-3-choosable (resp. 4-chromatic non-4-choosable) graphs of order at most 9 (resp. 11) and settle a question posed by Nelsen~(2019).