Partial list colouring of certain graphs (Q888600)

From MaRDI portal
Revision as of 23:36, 10 July 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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
    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

    Identifiers