Title

A New Bound On The Cyclic Chromatic Number

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 Δ of the graph. Some graphs require ⌊3/2Δ⌋ colors in an angular coloring. Ore and Plummer gave an upper bound of 2Δ, which was improved to ⌊9/5Δ⌋ by the authors with Borodin. This article gives a new upper bound of ⌈5/9Δ⌉ on the angular chromatic number. The cyclic chromatic number is the equivalent dual vertex coloring problem. © 2001 Academic Press.

Publication Date

1-1-2001

Publication Title

Journal of Combinatorial Theory. Series B

Volume

83

Issue

1

Number of Pages

102-111

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1006/jctb.2001.2046

Socpus ID

0035191181 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0035191181

This document is currently not available here.

Share

COinS