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
    0 references
    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
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references