✦ LIBER ✦

Equitable list-coloring for graphs of maximum degree 3

✍ Scribed by Michael J. Pelsmajer

Publisher: John Wiley and Sons
Year: 2004
Tongue: English
Weight: 102 KB
Volume: 47
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20011

No coin nor oath required. For personal study only.

✦ Synopsis

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(G)|/k⌉ vertices. A graph is equitably k‐choosable if such a coloring exists whenever the lists all have size k. Kostochka, Pelsmajer, and West introduced this notion and conjectured that G is equitably k‐choosable for k > Δ (G). We prove this for Δ(G) = 3. We also show that every graph G is equitably k‐choosable for k ≥ Δ(G)(Δ(G)−1)/2 + 2. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 1–8, 2004

📜 SIMILAR VOLUMES

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

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

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

Edge-face coloring of plane graphs with

Edge-face coloring of plane graphs with maximum degree nine

✍ Jean-Sébastien Sereni; Matěj Stehlík 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 189 KB 👁 1 views

An edge-face coloring of a plane graph with edge set E and face set F is a coloring of the elements of E ∪F so that adjacent or incident elements receive different colors. Borodin [Discrete Math 128(1-3): [21][22][23][24][25][26][27][28][29][30][31][32][33] 1994] proved that every plane graph of max

Total colorings of planar graphs with la

Total colorings of planar graphs with large maximum degree

✍ Borodin, O. V.; Kostochka, A. V.; Woodall, D. R. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 97 KB 👁 3 views

It is proved that a planar graph with maximum degree ∆ ≥ 11 has total (vertex-edge) chromatic number ∆ + 1.

3-List-Coloring Planar Graphs of Girth 5

✍ C. Thomassen 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 269 KB

We prove that every planar graph of girth at least 5 is 3-choosable. It is even possible to precolor any 5-cycle in the graph. This extension implies Grötzsch's theorem that every planar graph of girth at least 4 is 3-colorable. If 1995 Academic Press, Inc.