𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by H. A. Kierstead; A. V. Kostochka

Publisher
John Wiley and Sons
Year
2011
Tongue
English
Weight
299 KB
Volume
71
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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' theorem. Chen et al., proved that their conjecture holds for r = 3. In this article we study properties of the hypothetical minimum counter‐examples to this conjecture and the structure of “optimal” colorings of such graphs. Using these properties and structure, we show that the Chen–Lih–Wu Conjecture holds for r≤4. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:31–48, 2012

📜 SIMILAR VOLUMES

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

Very rapidly mixing Markov chains for 2Δ
Very rapidly mixing Markov chains for 2Δ-colorings and for independent sets in a graph with maximum degree 4
✍ Michael Molloy 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB 👁 1 views

We introduce a new technique for analyzing the mixing rate of Markov chains. We use it to prove that the Glauber dynamics on 2 -colorings of a graph with maximum degree mixes in O n log n time. We prove the same mixing rate for the Insert/Delete/Drag chain of Dyer and Greenhill (Random Structures A