✦ LIBER ✦

Equitable Coloring and the Maximum Degree

✍ Scribed by Bor-Liang Chen; Ko-Wei Lih; Pou-Lin Wu

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 184 KB
Volume: 15
Category: Article
ISSN: 0195-6698
DOI: 10.1006/eujc.1994.1047

No coin nor oath required. For personal study only.

✦ Synopsis

Let (\Delta(G)) denote the maximum degree of a graph (G). The equitable (\Delta)-coloring conjecture asserts that a connected graph (G) is equitably (\Delta(G))-colorable if it is different from (K_{m}, C_{2 m+1}) and (K_{2 m+1,2 m+1}) for all (m \geqslant 1). This conjecture is established for graphs (G) satisfying (\Delta(G) \geqslant|G| / 2) or (\Delta(G) \leqslant 3).

📜 SIMILAR VOLUMES

Equitable list-coloring for graphs of ma

Equitable list-coloring for graphs of maximum degree 3

✍ Michael J. Pelsmajer 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 102 KB

## Abstract Given lists of available colors assigned to the vertices of a graph __G__, a list coloring is a proper coloring of __G__ such that the color on each vertex is chosen from its list. If the lists all have size __k__, then a list coloring is equitable if each color appears on at most ⌈|__V

Every 4-Colorable Graph With Maximum Deg

Every 4-Colorable Graph With Maximum Degree 4 Has an Equitable 4-Coloring

✍ H. A. Kierstead; A. V. Kostochka 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 299 KB

## Abstract Chen et al., conjectured that for __r__≥3, the only connected graphs with maximum degree at most __r__ that are not equitably __r__‐colorable are __K__~__r, r__~ (for odd __r__) and __K__~__r__ + 1~. If true, this would be a joint strengthening of the Hajnal–Szemerédi theorem and Brooks

Equitable list coloring and treewidth

✍ Michael J. Pelsmajer 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 143 KB

## Abstract Given lists of available colors assigned to the vertices of a graph __G__, a __list coloring__ is a proper coloring of __G__ such that the color on each vertex is chosen from its list. If the lists all have size __k__, then a list coloring is __equitable__ if each color appears on at mo

Acyclic edge coloring of graphs with max

Acyclic edge coloring of graphs with maximum degree 4

✍ Manu Basavaraju; L. Sunil Chandran 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB 👁 1 views

## Abstract An __acyclic__ edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The __acyclic chromatic index__ of a graph is the minimum number __k__ such that there is an acyclic edge coloring using __k__ colors and is denoted by __a__′(__G__). It was conj

A list analogue of equitable coloring

✍ A. V. Kostochka; M. J. Pelsmajer; D. B. West 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB

On total 9-coloring planar graphs of max

On total 9-coloring planar graphs of maximum degree seven

✍ Sanders, Daniel P.; Zhao, Yue 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB 👁 3 views

Given a graph G, a total k-coloring of G is a simultaneous coloring of the vertices and edges of G with at most k colors. If ∆(G) is the maximum degree of G, then no graph has a total ∆-coloring, but Vizing conjectured that every graph has a total (∆ + 2)-coloring. This Total Coloring Conjecture rem