The number of k-colorings of a graph on a fixed surface

    Research output: Contribution to journalConference articleResearchpeer-review

    Abstract

    We prove that, for every fixed surface S, there exists a largest positive constant c such that every 5-colorable graph with n vertices on S has at least c center dot 2(n) distinct 5-colorings. This is best possible in the sense that, for each sufficiently large natural number n, there is a graph with n vertices on S that has precisely c center dot 2(n) distinct 5-colorings. For the sphere the constant c is 15/2, and for each other surface, it is a finite problem to determine c. There is an analogous result for k-colorings for each natural number k > 5. (c) 2006 Elsevier B.V. All rights reserved.
    Original languageEnglish
    JournalDiscrete Mathematics
    Volume306
    Issue number23
    Pages (from-to)3145-3153
    ISSN0012-365X
    DOIs
    Publication statusPublished - 2006
    EventConference of the European Membrane Society 2006 - Giardini Naxos, Italy
    Duration: 24 Sep 200628 Sep 2006
    http://euromembrane2006.itm.cnr.it/

    Conference

    ConferenceConference of the European Membrane Society 2006
    CountryItaly
    CityGiardini Naxos
    Period24/09/200628/09/2006
    SponsorUniversity of Calabria
    Internet address

    Keywords

    • Chromatic polynomial
    • Graphs on surfaces

    Fingerprint Dive into the research topics of 'The number of k-colorings of a graph on a fixed surface'. Together they form a unique fingerprint.

    Cite this