Coloring triangle-free graphs with fixed size

Carsten Thomassen, John Gimbel

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    Combining recent results on colorings and Ramsey theory, we show that if G is a triangle-free graph with e edges then the chromatic number of G is at most cel(1/3)(log e)(-2/3) for some constant c. In a previous paper, we found an upper bound on the chromatic number of a triangle-free graph of genus g. Using the new result, we slightly improve this bound to cg(1/3)(log g)(-2/3). Both bounds are best possible, up to a constant multiple. (C) 2000 Elsevier Science B.V. All rights reserved.
    Original languageEnglish
    JournalDiscrete Mathematics
    Volume219
    Issue number1-3
    Pages (from-to)275-277
    ISSN0012-365X
    DOIs
    Publication statusPublished - 2000

    Cite this