Chromatic number versus chromatic number in graphs with bounded clique number (Q2640609): Difference between revisions
From MaRDI portal
Created a new Item |
Created claim: Wikidata QID (P12): Q105529936, #quickstatements; #temporary_batch_1704697335568 |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q105529936 / rank | |||
Normal rank |
Revision as of 08:12, 8 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Chromatic number versus chromatic number in graphs with bounded clique number |
scientific article |
Statements
Chromatic number versus chromatic number in graphs with bounded clique number (English)
0 references
1990
0 references
The cochromatic number \(z(G)\) of a graph \(G\) is the minimum number of sets into which the vertices of \(G\) can be partitioned so that each set is independent in \(G\) or induces a complete subgraph of \(G\). The present paper proves the existence ofa function \(f(n)\) with the following property: If \(G\) does not contain a complete \(n\)-graph \(K_n\) and \(G\neq K_{n-1}\), then the usual chromatic number \(\chi(G)\) is at most \(z(G)+f(n)\). Moreover it is proved that \(f(n)\) is exponential in \(n\) and that \(f(3)=1\) and \(f(4)=1\).
0 references
clique number
0 references
cochromatic number
0 references