On coloring graphs with locally small chromatic number (Q759761): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claim: author (P16): Item:Q792346
RedirectionBot (talk | contribs)
Changed an Item
Property / author
 
Property / author: William T. jun. Trotter / rank
 
Normal rank

Revision as of 21:27, 20 February 2024

scientific article
Language Label Description Also known as
English
On coloring graphs with locally small chromatic number
scientific article

    Statements

    On coloring graphs with locally small chromatic number (English)
    0 references
    0 references
    0 references
    1984
    0 references
    It is proved that for each pair of positive integers c and k, if G is a graph on n vertices with no subgraph H, whose chromatic number is greater than c and whose radius in G is at most \(2kn^{1/k}\), then the chromatic number of G is at most \(k(c-1)+1\). As a special case a conjecture of \textit{P. Erdős} is settled in the affirmative [see Graph theory and related topics, Proc. Conf. Honour W. T. Tutte, Waterloo/Ont. 1977, 153-163 (1979; Zbl 0457.05024)].
    0 references
    0 references
    chromatic number
    0 references

    Identifiers