Partial list colouring of certain graphs (Q888600)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Partial list colouring of certain graphs |
scientific article |
Statements
Partial list colouring of certain graphs (English)
0 references
2 November 2015
0 references
Summary: The partial list colouring conjecture due to \textit{M. O. Albertson} et al. [Discrete Math. 214, No. 1--3, 235--240 (2000; Zbl 0957.05037)] states that for every \(s\)-choosable graph \(G\) and every assignment of lists of size \(t\), \(1 \leq t \leq s\), to the vertices of \(G\) there is an induced subgraph of \(G\) on at least \(\frac{t|V(G)|}{s}\) vertices which can be properly coloured from these lists. In this paper, we show that the partial list colouring conjecture holds true for certain classes of graphs like claw-free graphs, graphs with chromatic number at least \(\frac{|V(G)|-1}{2}\), chordless graphs, and series-parallel graphs.
0 references
partial list colouring conjecture
0 references
claw-free graph
0 references
series-parallel graph
0 references
chordless graph
0 references
treewidth
0 references
choosability
0 references