On a list-coloring problem (Q1398274)

From MaRDI portal
Revision as of 18:31, 5 June 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
On a list-coloring problem
scientific article

    Statements

    On a list-coloring problem (English)
    0 references
    0 references
    0 references
    0 references
    29 July 2003
    0 references
    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}\).
    0 references
    0 references
    list-coloring
    0 references
    join
    0 references
    list-chromatic number
    0 references
    \(k\)-choosable graph
    0 references
    0 references