No Arabic abstract
A graph $G$ is called $3$-choice critical if $G$ is not $2$-choosable but any proper subgraph is $2$-choosable. A characterization of $3$-choice critical graphs was given by Voigt in [On list Colourings and Choosability of Graphs, Habilitationsschrift, Tu Ilmenau(1998)]. Voigt conjectured that if $G$ is a bipartite $3$-choice critical graph, then $G$ is $(4m, 2m)$-choosable for every integer $m$. This conjecture was disproved by Meng, Puleo and Zhu in [On (4, 2)-Choosable Graphs, Journal of Graph Theory 85(2):412-428(2017)]. They showed that if $G=Theta_{r,s,t}$ where $r,s,t$ have the same parity and $min{r,s,t} ge 3$, or $G=Theta_{2,2,2,2p}$ with $p ge 2$, then $G$ is bipartite $3$-choice critical, but not $(4,2)$-choosable. On the other hand, all the other bipartite 3-choice critical graphs are $(4,2)$-choosable. This paper strengthens the result of Meng, Puleo and Zhu and shows that all the other bipartite $3$-choice critical graphs are $(4m,2m)$-choosable for every integer $m$.
This paper disproves a conjecture of Wang, Wu, Yan and Xie, and answers in negative a question in Dvorak, Pekarek and Sereni. In return, we pose five open problems.
3-list colouring is an NP-complete decision problem. It is hard even on planar bipartite graphs. We give a polynomial-time algorithm for solving 3-list colouring on permutation graphs.
A graph $G$ is called $3$-choice critical if $G$ is not $2$-choosable but any proper subgraph is $2$-choosable. A graph $G$ is strongly fractional $r$-choosable if $G$ is $(a,b)$-choosable for all positive integers $a,b$ for which $a/b ge r$. The strong fractional choice number of $G$ is $ch_f^s(G) = inf {r: G $ is strongly fractional $r$-choosable$}$. This paper determines the strong fractional choice number of all $3$-choice critical graphs.
A (not necessarily proper) vertex colouring of a graph has clustering $c$ if every monochromatic component has at most $c$ vertices. We prove that planar graphs with maximum degree $Delta$ are 3-colourable with clustering $O(Delta^2)$. The previous best bound was $O(Delta^{37})$. This result for planar graphs generalises to graphs that can be drawn on a surface of bounded Euler genus with a bounded number of crossings per edge. We then prove that graphs with maximum degree $Delta$ that exclude a fixed minor are 3-colourable with clustering $O(Delta^5)$. The best previous bound for this result was exponential in $Delta$.
List colouring is an NP-complete decision problem even if the total number of colours is three. It is hard even on planar bipartite graphs. We give a polynomial-time algorithm for solving list colouring of permutation graphs with a bounded total number of colours. More generally we give a polynomial-time algorithm that solves the list-homomorphism problem to any fixed target graph for a large class of input graphs including all permutation and interval graphs.