𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Upper Bounds of Entire Chromatic Number of Plane Graphs

✍ Scribed by W. Weifan

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
35 KB
Volume
20
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

The entire chromatic number Ο‡ ve f (G) of a plane graph G is the least number of colors assigned to the vertices, edges and faces so that every two adjacent or incident pair of them receive different colors. conjectured that Ο‡ ve f (G) ≀ + 4 for every plane graph G.

In this paper we prove the conjecture for a plane graph G having Ο‡ (G) = and give a upper bound Ο‡ ve f (G) ≀ + 5 for all plane graphs, where Ο‡ (G) and are the chromatic index and the maximum degree of G, respectively.

πŸ“œ SIMILAR VOLUMES

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

Upper chromatic number of finite project
Upper chromatic number of finite projective planes
✍ GΓ‘bor BacsΓ³; Zsolt Tuza πŸ“‚ Article πŸ“… 2008 πŸ› John Wiley and Sons 🌐 English βš– 135 KB

## Abstract For a finite projective plane $\Pi$, let $\bar {\chi} (\Pi)$ denote the maximum number of classes in a partition of the point set, such that each line has at least two points in the same partition class. We prove that the best possible general estimate in terms of the order of projectiv

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

New bounds for the chromatic number of g
New bounds for the chromatic number of graphs
✍ Manouchehr Zaker πŸ“‚ Article πŸ“… 2008 πŸ› John Wiley and Sons 🌐 English βš– 184 KB πŸ‘ 1 views

## Abstract In this article we first give an upper bound for the chromatic number of a graph in terms of its degrees. This bound generalizes and modifies the bound given in 11. Next, we obtain an upper bound of the order of magnitude ${\cal O}({n}^{{1}-\epsilon})$ for the coloring number of a graph