On the chromatic number of pentagon-free graphs of large minimum degree

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    We prove that, for each fixed real number c > 0, the pentagon-free graphs of minimum degree at least cn (where n is the number of vertices) have bounded chromatic number. This problem was raised by Erdős and Simonovits in 1973. A similar result holds for any other fixed odd cycle, except the triangle for which there is no such result for c<1/3.
    Original languageEnglish
    JournalCombinatorica
    Volume27
    Issue number2
    Pages (from-to)241-243
    ISSN0209-9683
    DOIs
    Publication statusPublished - 2007

    Keywords

    • 05C15

    Fingerprint

    Dive into the research topics of 'On the chromatic number of pentagon-free graphs of large minimum degree'. Together they form a unique fingerprint.

    Cite this