Extension of a list coloring problem (Q2488686)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Extension of a list coloring problem |
scientific article |
Statements
Extension of a list coloring problem (English)
0 references
11 May 2006
0 references
For a graph \(G\), let \(f(G)\) be the minimum integer \(k\) such that the graph formed from \(G\) by adding \(k\) independent vertices and joining each of them with all vertices of \(G\) is not \(| V(G)| \)-choosable. The quantity \(f(G)\) is related to some properties of Nordhaus-Gaddum type and it was studied previously by \textit{S. Gravier, F. Maffray}, and \textit{B. Mohar} [Discrete Math. 268, 303--308 (2003; Zbl 1018.05028)] who proposed a general conjecture on the value of \(f(G)\). If \(G\) is a triangle-free graph of order \(n\), their conjecture asserts that \(f(G) = {n\choose 2}^{\mu(G)} n^{n-2\mu(G)}\), where \(\mu(G)\) is the size of the maximum matching of \(G\). Gravier et al. proved that their conjecture holds for trees, and the authors of the paper under review extend the result to all forests.
0 references
list coloring
0 references
choosability
0 references
choice number
0 references