On a list-coloring problem (Q1398274): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 04:12, 5 March 2024
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
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
list-coloring
0 references
join
0 references
list-chromatic number
0 references
\(k\)-choosable graph
0 references