✦ LIBER ✦

Acyclic edge coloring of 2-degenerate graphs

✍ Scribed by Manu Basavaraju; L. Sunil Chandran

Publisher: John Wiley and Sons
Year: 2010
Tongue: English
Weight: 280 KB
Volume: 69
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20559

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). A graph is called 2‐degenerate if any of its induced subgraph has a vertex of degree at most 2. The class of 2‐degenerate graphs properly contains series–parallel graphs, outerplanar graphs, non − regular subcubic graphs, planar graphs of girth at least 6 and circle graphs of girth at least 5 as subclasses. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a′(G)⩽Δ + 2, where Δ = Δ(G) denotes the maximum degree of the graph. We prove the conjecture for 2‐degenerate graphs. In fact we prove a stronger bound: we prove that if G is a 2‐degenerate graph with maximum degree Δ, then a′(G)⩽Δ + 1. © 2010 Wiley Periodicals, Inc. J Graph Theory 69: 1–27, 2012

📜 SIMILAR VOLUMES

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′__(_

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

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

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

Semistrong edge coloring of graphs

✍ András Gyárfás; Alice Hubenko 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB

## Abstract Weakening the notion of a strong (induced) matching of graphs, in this paper, we introduce the notion of a semistrong matching. A matching __M__ of a graph __G__ is called semistrong if each edge of __M__ has a vertex, which is of degree one in the induced subgraph __G__[__M__]. We stre

Optimal edge coloring of large graphs

✍ G�mez, J.; Escudero, M. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 95 KB 👁 3 views

Most of the general families of large considered graphs in the context of the so-called (⌬, D) problem-that is, how to obtain graphs with maximum order, given their maximum degree ⌬ and their diameter D-known up to now for any value of ⌬ and D, are obtained as product graphs, compound graphs, and ge