✦ LIBER ✦

Acyclic edge coloring of graphs with maximum degree 4

✍ Scribed by Manu Basavaraju; L. Sunil Chandran

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 168 KB
Volume: 61
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20376

No coin nor oath required. For personal study only.

✦ Synopsis

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 conjectured by Alon, Sudakov, and Zaks that for any simple and finite graph G, a′(G)⩽Δ + 2, where Δ=Δ(G) denotes the maximum degree of G. We prove the conjecture for connected graphs with Δ(G)⩽4, with the additional restriction that m⩽2__n__−1, where n is the number of vertices and m is the number of edges in G. Note that for any graph G, m⩽2__n__, when Δ(G)⩽4. It follows that for any graph G if Δ(G)⩽4, then a′(G)⩽7. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 192–209, 2009

📜 SIMILAR VOLUMES

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

Acyclic edge colorings of graphs

✍ Noga Alon; Benny Sudakov; Ayal Zaks 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 102 KB

## Abstract A proper coloring of the edges of a graph __G__ is called __acyclic__ if there is no 2‐colored cycle in __G__. The __acyclic edge chromatic number__ of __G__, denoted by __a′__(__G__), is the least number of colors in an acyclic edge coloring of __G__. For certain graphs __G__, __a′__(_

Acyclic edge coloring of 2-degenerate gr

Acyclic edge coloring of 2-degenerate graphs

✍ Manu Basavaraju; L. Sunil Chandran 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 280 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__). A graph is

Optimal acyclic edge-coloring of cubic g

Optimal acyclic edge-coloring of cubic graphs

✍ Lars Døvling Andersen; Edita Máčajová;; Ján Mazák 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 194 KB

An __acyclic edge‐coloring__ of a graph is a proper edge‐coloring such that the subgraph induced by the edges of any two colors is acyclic. The __acyclic chromatic index__ of a graph __G__ is the smallest number of colors in an acyclic edge‐coloring of __G__. We prove that the acyclic chromatic inde

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 triangle-free p

Acyclic edge coloring of triangle-free planar graphs

✍ Manu Basavaraju; L. Sunil Chandran 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 233 KB 👁 2 views

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 conjectured by Al