On a list-coloring problem (Q1398274): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / cites work | |||
Property / cites work: Extremal graphs for the list-coloring version of a theorem of Nordhaus and Gaddum / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3922703 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3115277 / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0012-365x(03)00033-5 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1985935983 / rank | |||
Normal rank |
Latest revision as of 09:37, 30 July 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