Chromatic number versus chromatic number in graphs with bounded clique number (Q2640609): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
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
    0 references
    0 references
    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
    0 references
    clique number
    0 references
    cochromatic number
    0 references

    Identifiers