𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An upper bound for the total chromatic number of dense graphs

✍ Scribed by H. R. Hind

Publisher
John Wiley and Sons
Year
1992
Tongue
English
Weight
340 KB
Volume
16
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 show that if the maximum degree of a graph G satisfies Ξ”(G) β‰₯ |V(G)/k, then Xβ€³(G) ≀ Ξ”(G) + 2__k__ + 1. This upper bound is an improvement on the currently available upper bounds for dense graphs having large order.

πŸ“œ 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

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.

Upper Bounds of Entire Chromatic Number
Upper Bounds of Entire Chromatic Number of Plane Graphs
✍ W. Weifan πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 35 KB

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 conj

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

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