𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The acyclic edge chromatic number of a random d-regular graph is d + 1

✍ Scribed by Jaroslav Nešetřil; Nicholas C. Wormald

Publisher
John Wiley and Sons
Year
2005
Tongue
English
Weight
67 KB
Volume
49
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We prove the theorem from the title: the acyclic edge chromatic number of a random d‐regular graph is asymptotically almost surely equal to d + 1. This improves a result of Alon, Sudakov, and Zaks and presents further support for a conjecture that Δ(G) + 2 is the bound for the acyclic edge chromatic number of any graph G. It also represents an analog of a result of Robinson and the second author on edge chromatic number. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 69–74, 2005

📜 SIMILAR VOLUMES

The generalized acyclic edge chromatic n
The generalized acyclic edge chromatic number of random regular graphs
✍ Stefanie Gerke; Catherine Greenhill; Nicholas Wormald 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 224 KB 👁 1 views

## Abstract The __r__‐acyclic edge chromatic number of a graph is defined to be the minimum number of colors required to produce an edge coloring of the graph such that adjacent edges receive different colors and every cycle __C__ has at least min(|__C__|, __r__) colors. We show that (__r__ − 2)__d

On the chromatic number of a random 5-re
On the chromatic number of a random 5-regular graph
✍ J. Díaz; A. C. Kaporis; G. D. Kemkes; L. M. Kirousis; X. Pérez; N. Wormald 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 275 KB 👁 1 views

## Abstract It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5‐regular graph asymptotically almost surely has chromatic number at most 4. Here, we show that the chromatic number of a random 5‐regular graph is as