Choice number of 3-colorable elementary graphs

DOI10.1016/S0012-365X(96)00182-3MaRDI QIDQ1356789zbMATH OpenOpenAlexWikidataFDO

Authors Sylvain Gravier, Frédéric Maffray

Publication date 1 June 1998

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(96)00182-3

zbMATH Keywords

choice numberclaw-free graphslist-chromatic conjecture

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph theory (including graph drawing) in computer science (68R10)

Review text

The choice number \(\text{ch}(G)\) of a graph \(G= (V,E)\) is the smallest number \(k\) for which, for any assignment of a list \(L(v)\) of \(k\) colors to every vertex \(v\in V\), it is possible to color properly the vertices of \(G\) so that every vertex gets a color from its list. Certainly, \(\chi(G)\leq \text{ch}(G)\) for every graph \(G\), with equality holding true for trees, cycles, wheels, line-graphs of bipartite graphs and complements of triangle-free graphs, to mention just a few examples. The authors show that \(\chi(G)= \text{ch}(G)\) if \(G\) belongs to a restricted family of claw-free graphs, namely to the so-called elementary graphs with \(\omega(G)\leq 3\). This result supports their conjecture that every claw-free graph \(G\) satisfies the choice chromatic equality, which is more general than the well-known list-chromatic conjecture.

Recommendations

• On the choosability of claw-free perfect graphs
• scientific article; zbMATH DE number 1123764
• Claw-free graphs. VI: Colouring
• List-coloring claw-free graphs with small clique number

Cites work

• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• Recognizing claw-free perfect graphs
• Some upper bounds on the total and list chromatic numbers of multigraphs
• The list chromatic index of a bipartite multigraph

Cited in

(14)

• On the choice number of claw-free perfect graphs
• List coloring a Cartesian product with a complete bipartite factor
• Towards an on-line version of Ohba's conjecture
• Choice-perfect graphs
• Application of polynomial method to on-line list colouring of graphs
• On chromatic‐choosable graphs
• Chromatic-choosability of the power of graphs
• On the choosability of claw-free perfect graphs
• A proof of a conjecture of Ohba
• Claw-free graphs. VI: Colouring
• On the Alon-Tarsi number and chromatic-choosability of Cartesian products of graphs
• Chromatic-choosability of hypergraphs with high chromatic number
• Minimum non-chromatic--choosable graphs (extended abstract)
• List-coloring claw-free graphs with small clique number

This page was built for publication: Choice number of 3-colorable elementary graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1356789)