论文标题
列表方形着色的猜想失败了两分的平面图及其线图
The List Square Coloring Conjecture fails for bipartite planar graphs and their line graphs
论文作者
论文摘要
Kostochka and Woodall（2001）猜想每个图的平方都具有相同的色数和列表色编号。在2015年，金和公园对非双方和两部分图的这种猜想反驳了。几位作者询问该猜想是否适用于具有小度，无爪图或线图的两部分图。在本文中，我们向这个猜想介绍了几种反例，以解决Kim and Park〜（2015），Kim，Kwon和Park〜（2015）以及Dai，Wang，Yang和Yu〜（2018）提出的三个开放问题。特别是，我们反驳了Havet，Heuvel，McDiarmid和Reed（2017）提出的这个猜想的平面版本。 该猜想最初是为了使列表的总体着色猜想更强的版本。为了制作修订版，要决定这种猜想是否存在于两分的图形$ g $，通过对正方形图的变色数（$ g^2 $）的最大程度表示，因为条件$χ（g^2）\ ge \ ge \ ge \ ge \ frac {1} {1} {2} {2} {g^2}δ（g^2）+1 $ 1 $（或添加umpers of ins of affere）为了支持此版本，我们将证明即使任意增加下限也无法删除两分的条件。 最后，我们研究了两分或平面图中具有界限最大程度的非选择图。因此，由于Erd \ H OS，Rubin和Taylor〜（1980），Bessy，Havet和Palaysi（2002），Voigt（1993），Mirzakhani（1996）和Glebov，Glebov，Kostochka和Tashkinkinov（2005）（2005年），我们改善了几种图形结构。此外，我们表征了边缘最小的$ 3 $ -CHROMATIC非$ 3 $ -Choosable（resp。$ 4 $ -CHROMATIC NON-$ 4 $ - choosable）订单图，最多为$ 9 $（$ 11 $），并解决了Nelsen〜（2019年）提出的问题。
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 $G^2$ in terms of its maximum degree as the condition $χ(G^2) \ge \frac{1}{2} Δ(G^2)+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).
