List colourings of graphs
A list colouring of a graph is a colouring in which each vertex \(v\) receives a colour from a prescribed list \(L(v)\). The list-chromatic number or choosability \(\text{ch}(G)\) is the smallest \(k\) such that a graph always has a proper list colouring provided the prescribed lists are of size at least \(k\). If the lists are the same for each vertex, then \(\text{ch}(G)\) reduces to the usual chromatic number \(\chi(G)\). NEWLINENEWLINENEWLINEThis paper provides an excellent survey of list colourings. A section is devoted to results and conjectures regarding when \(\text{ch}(G) = \chi (G)\). Some time is spent on \((a:b)\)-choosability: each vertex gets a list of \(a\) colours, and we must choose \(b\) of these colours so that adjacent vertices receive disjoint sets. The author also examines \(d\)-defective colourings, where the subgraph induced by vertices receiving a fixed colour has maximum degree \(d\). List versions of Hadwidger's conjecture are given, except in this context one excludes \(K_{r,s}\) minors instead of \(K_r\) minors. Some new results are given regarding defective choosability of planar graphs. Another variation adds the restriction that adjacent vertices have a bound on the number of elements in common in their lists. The paper concludes with a review of different methods of proof for choosability results and examines the strengths and weaknesses of each. NEWLINENEWLINENEWLINEThe paper is excellently written. It is clearly organized and offers a variety of conjectures and open problems. This is a ``must read for anyone interested in colouring graphs.NEWLINENEWLINEFor the entire collection see [Zbl 0964.00035].
- A note on list improper coloring of plane graphs
- Ohba's conjecture is true for graphs with independence number at most three
- Entire choosability of near-outerplane graphs
- List-coloring graphs without \(K_{4,k}\)-minors
- Graphic and protographic lists of integers
- Partial list colorings
- On group choosability of graphs. II
- Disproof of a conjecture by Woodall on the choosability of \(K_{s,t}\)-minor-free graphs
- On \(t\)-common list-colorings
- List supermodular coloring
- On choosability of some complete multipartite graphs and Ohba's conjecture
- List coloring of Cartesian products of graphs
- Sum list coloring graphs
- Ohba's conjecture is true for graphs \(K_{t+2,3,2\ast(k-t-2),1\ast t}\)
- List-colourings
- A note on total and list edge-colouring of graphs of tree-width 3
- List Coloring with a Bounded Palette
- List hereditary colorings of graphs (extended abstract)
- scientific article; zbMATH DE number 6000769 (Why is no real title available?)
- Colouring graphs on surfaces
- Graph colorings with local constraints -- a survey
- Defective choosability of graphs with no edge-plus-independent-set minor
- Beyond Ohba's conjecture: a bound on the choice number of \(k\)-chromatic graphs with \(n\) vertices
- List coloring digraphs
- Orientations of graphs with prescribed weighted out-degrees
- A proof of a conjecture of Ohba
- Introduction to list colourings
- Coloring graphs from lists with bounded size of their union
- List colouring when the chromatic number is close to the order of the graph
- List-coloring embedded graphs
- On the complexity of some colorful problems parameterized by treewidth
- Biclique immersions in graphs with independence number 2
- On the choosability of \(H\)-minor-free graphs
- On two problems of defective choosability of graphs
- New counterexamples to a conjecture by Woodall on graph minors and list coloring
- Complete bipartite immersion in graphs with independence number two: a simple proof
- Limits of degeneracy for colouring graphs with forbidden minors
- Seymour and Woodall's conjecture holds for graphs with independence number two
- Biclique immersions in graphs with independence number 2 (extended abstract)
- Dense graphs have \(K_{3,t}\) minors
- Contractibility and the Hadwiger conjecture
- Odd complete bipartite minors in graphs with independence number two
- Tight minimum degree conditions for apex-outerplanar minors and subdivisions in graphs and digraphs
- Precoloring extension with demands on paths
- Partial list colouring of certain graphs
- List-colouring the square of a \(K_4\)-minor-free graph
- The average degree of a multigraph critical with respect to edge or total choosability
- List-edge and list-total colorings of graphs embedded on hyperbolic surfaces
- Choice number of complete multipartite graphs \(K_{3*3,2*(k - 5),1*2}\) and \(K_{4,3*2,2*(k - 6),1*3}\)
This page was built for publication: List colourings of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2741180)
