List-colourings
A \(k\)-list assignment \(L\) is an assignment of sets, which are also called lists to the vertices \(v\mapsto L(v)\) such that \(|L(v)|=k\); for all vertices \(v\). An \(L\)-list coloring is a coloring such that the color assigned to \(v\) is in \(L(v)\) for all vertices \(v\). A graph \(G\) which admits an \(L\)-list coloring is called a list colorable graph. The list chromatic number \(\chi_{\ell}(G)\) of a graph \(G\) is the minimum value of \(k\) such that \(G\) is \(k\)-list colourable. In this paper, the authors review the literature written on the list coloring of different graph classes. In the introductory section, the authors present the terminology, fundamental results and conjectures provided in the existing literature. In the second section, the authors consolidate the studies on the graphs whose orientations have certain properties. The studies on the list colouring properties of planar graphs have been reviewed in detail in the third section. The list colorings of planar bipartite graphs are discussed first and the reviews on 5-list colorability of planar graphs, the 4-list colorability of planar graph with forbidden cycles and 3-list colorability of triangle-free planar graphs followed in this section. After these topics, the terms and results of the edge list colorings of planar graphs and open problems in this area, including Richter's planar graph problem, are also explained in the third section. In the fourth section, the studies on the extended colorings of induced subgraphs of graphs to the entire graphs and certain interesting open problems are written in detail. In the final section, an extended analysis of the studies on list colouring and allied topics of graphs have been done. some interesting studies on 3-list critical graphs have also been written in this section. This article is a well-prepared survey in the research area concerned. A researcher who wish to study list coloring problem will find this paper highly useful as it covers a large number of papers written on this area and many conjectures and open problems are listed in this article.NEWLINENEWLINEFor the entire collection see [Zbl 1317.05004].
- The list chromatic numbers of some planar graphs
- On \(t\)-common list-colorings
- List colourings of graphs
- List colorings of K₅-minor-free graphs with special list assignments
- Graph colorings with local constraints -- a survey
- List coloring digraphs
- scientific article; zbMATH DE number 7637228 (Why is no real title available?)
- List coloring with requests
- Introduction to list colourings
- Packing list‐colorings
- Degree-truncated choosability of graphs
This page was built for publication: List-colourings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2822593)
