Extension of a list coloring problem

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.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Extension of a list coloring problem

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