𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by Hikoe Enomoto; Mirko Horňák

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
457 KB
Volume
62
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 and Toft in 1987 that, for every 3‐connected plane graph G, χ~c~(G)≤Δ^*^(G) + 2, where Δ^*^(G) is the maximum face degree of G. The best upper bound known so far was Δ^*^(G) + 8. In the paper this bound is improved to Δ^*^(G) + 5. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 1–25, 2009

📜 SIMILAR VOLUMES

An upper bound for the harmonious chroma
An upper bound for the harmonious chromatic number of a graph
✍ Sin-Min Lee; John Mitchem 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 149 KB 👁 2 views

An upper bound for the harmonious chromatic number of a graph G is given. Three corollaries of the theorem are theorems or improvements of the theorems of Miller and Pritikin. The assignment of colors to the vertices of a graph such that each vertex has exactly one color has been studied for well o

An upper bound for the total chromatic n
An upper bound for the total chromatic number of dense graphs
✍ H. R. Hind 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 340 KB 👁 1 views

## Abstract In this paper we consider those graphs that have maximum degree at least 1/__k__ times their order, where __k__ is a (small) positive integer. A result of Hajnal and Szemerédi concerning equitable vertex‐colorings and an adaptation of the standard proof of Vizing's Theorem are used to s

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

Bounds for the harmonious chromatic numb
Bounds for the harmonious chromatic number of a graph
✍ I. Krasikov; Y. Roditty 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 231 KB 👁 2 views

## Abstract The upper bound for the harmonious chromatic number of a graph given by Zhikang Lu and by C. McDiarmid and Luo Xinhua, independently (__Journal of Graph Theory__, 1991, pp. 345–347 and 629–636) and the lower bound given by D. G. Beane, N. L. Biggs, and B. J. Wilson (__Journal of Graph T