Partial list colouring of certain graphs (Q888600)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 6502784
Language Label Description Also known as
default for all languages
No label defined
    English
    Partial list colouring of certain graphs
    scientific article; zbMATH DE number 6502784

      Statements

      Partial list colouring of certain graphs (English)
      0 references
      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