On a list-coloring problem

DOI10.1016/S0012-365X(03)00033-5MaRDI QIDQ1398274zbMATH OpenOpenAlexFDO

Authors Sylvain Gravier, Frédéric Maffray, Bojan Mohar

Publication date 29 July 2003

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(03)00033-5

zbMATH Keywords

\(k\)-choosable graphjoinlist-chromatic numberlist-coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35)

Review text

In this paper the function \(f(G)\) is defined for a graph \(G\) as the smallest integer \(k\) such that the join of \(G\) with a stable set of size \(k\) is not \(|V(G)|\)-choosable. This function was introduced recently in order to describe extremal graphs for a list-coloring version of a famous inequality due to Nordhaus and Gaddum (Dantas et al., Research Report 18, Laboratoire Leibniz-IMAG, Grenoble, 2000). Some bounds and some exact values for \(f(G)\) are determined, e.g., if a graph \(G\) of order \(n\) is not complete, then \(f(G)\geq n^{2}\).

Recommendations

• Extension of a list coloring problem
• Extremal graphs for the list-coloring version of a theorem of Nordhaus and Gaddum
• Sum list coloring block graphs
• scientific article; zbMATH DE number 5630198
• List colorings with distinct list sizes, the case of complete bipartite graphs

Cites work

• Extremal graphs for the list-coloring version of a theorem of Nordhaus and Gaddum
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• Multicriterial graph problems with MAXMIN criterion

Cited in

(6)

• Extremal graphs for the list-coloring version of a theorem of Nordhaus and Gaddum
• Extension of a list coloring problem
• List-colourings
• Extremal decompositions for Nordhaus-Gaddum theorems
• On the Ohba number and generalized Ohba numbers of complete bipartite graphs
• Choice number and energy of graphs

This page was built for publication: On a list-coloring problem

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