✦ LIBER ✦

A new upper bound on the cyclic chromatic number

✍ Scribed by O. V. Borodin; H. J. Broersma; A. Glebov; J. van den Heuvel

Publisher: John Wiley and Sons
Year: 2006
Tongue: English
Weight: 160 KB
Volume: 54
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20193

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A cyclic coloring of a plane graph is a vertex coloring such that vertices incident with the same face have distinct colors. The minimum number of colors in a cyclic coloring of a graph is its cyclic chromatic number χ^c^. Let Δ^*^ be the maximum face degree of a graph. There exist plane graphs with χ^c^ = ⌊3/2 Δ^*^⌋. Ore and Plummer [5] proved that χ^c^ ≤ 2, Δ^*^, which bound was improved to ⌊9/5, Δ^*^⌋ by Borodin, Sanders, and Zhao [1], and to ⌈5/3,Δ^*^⌉ by Sanders and Zhao [7]. We introduce a new parameter k^*^, which is the maximum number of vertices that two faces of a graph can have in common, and prove that χ^c^ ≤ max {Δ^*^ + 3,k^*^ + 2, Δ^*^ + 14, 3, k^*^ + 6, 18}, and if Δ^*^ ≥ 4 and k^*^ ≥ 4, then χ^c^ ≤ Δ^*^ + 3,k^*^ + 2. © 2006 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

A New Bound on the Cyclic Chromatic Numb

A New Bound on the Cyclic Chromatic Number

✍ Daniel P. Sanders; Yue Zhao 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 116 KB

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 2 of the graph. Some graphs require w 3 2 2x colors in a

A new upper bound for the harmonious chr

A new upper bound for the harmonious chromatic number

✍ Edwards, Keith 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 200 KB 👁 2 views

A harmonious coloring of a simple graph G is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number h(G) is the least number of colors in such a coloring. We obtain a new upper bound for the harmonious chromatic number of general

New upper bounds for the chromatic numbe

New upper bounds for the chromatic number of a graph

✍ Ladislav Stacho 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 55 KB 👁 3 views

A general upper bound for the cyclic chr

A general upper bound for the cyclic chromatic number of 3-connected plane graphs

✍ Hikoe Enomoto; Mirko Horňák 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 457 KB 👁 1 views

## Abstract The cyclic chromatic number of a plane graph __G__ is the smallest number χ~__c__~(__G__) of colors that can be assigned to vertices of __G__ in such a way that whenever two distinct vertices are incident with a common face, they receive distinct colors. It was conjectured by Plummer an

On an upper bound for the harmonious chr

On an upper bound for the harmonious chromatic number of a graph

✍ Zhikang Lu 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB 👁 2 views

## Abstract The upper bound for the harmonious chromatic number of a graph that has been given by Sin‐Min Lee and John Mitchem is improved.

A new upper bound for the independence n

A new upper bound for the independence number of edge chromatic critical graphs

✍ Rong Luo; Yue Zhao 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 107 KB 👁 2 views

In 1968, Vizing conjectured that if G is a -critical graph with n vertices, then (G) ≤ n / 2, where (G) is the independence number of G. In this paper, we apply Vizing and Vizing-like adjacency lemmas to this problem and prove that (G)<(((5 -6)n) / (8 -6))<5n / 8 if ≥ 6. ᭧ 2010 Wiley