A new bound on the cyclic chromatic number

    Authors

    D. P. Sanders;Y. Zhao

    Abbreviated Journal Title

    J. Comb. Theory Ser. B

    Keywords

    Mathematics

    Abstract

    In 1969, Ore and Plummer defined an angular coloring as a natural extension of the Four Color Problem: a face coloring of a plane graph where faces meeting even at a vertex must have distinct colors. A natural lower bound is the maximum degree Delta of the graph. Some graphs require left perpendicular 3/2 Delta right perpendicular colors in an angular coloring. Ore and Plummer gave an upper bound of 2 Delta, which was improved to left perpendicular 9/5 right perpendicular by the authors with Borodin. This article gives a new upper bound of inverted right perpendicular 5/9 Delta inverted left perpendicular on the angular chromatic number. The cyclic chromatic number is the equivalent dual vertex coloring problem. (C) 2001 Academic Press.

    Journal Title

    Journal of Combinatorial Theory Series B

    Volume

    83

    Issue/Number

    1

    Publication Date

    1-1-2001

    Document Type

    Article

    Language

    English

    First Page

    102

    Last Page

    111

    WOS Identifier

    WOS:000171030500006

    ISSN

    0095-8956

    Share

    COinS