The acyclic edge chromatic number of A Random d-regular graph Is d+ 1

Jaroslav Nešetřil; Nicholas C. Wormald

doi:10.1002/jgt.20064

The acyclic edge chromatic number of A Random d-regular graph Is d+ 1

Jaroslav Nešetřil, Nicholas C. Wormald

Research output: Contribution to journal › Article › Research › peer-review

39 Citations (Scopus)

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.

Original language	English
Pages (from-to)	69-74
Number of pages	6
Journal	Journal of Graph Theory
Volume	49
Issue number	1
DOIs	https://doi.org/10.1002/jgt.20064
Publication status	Published - May 2005
Externally published	Yes

Keywords

Acyclic coloring
Coloring
Edge coloring
Random graphs
Regular graphs

Access to Document

10.1002/jgt.20064

Cite this

@article{feb6e237a504422eb91d5610b183dbc0,

title = "The acyclic edge chromatic number of A Random d-regular graph Is d+ 1",

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.",

keywords = "Acyclic coloring, Coloring, Edge coloring, Random graphs, Regular graphs",

author = "Jaroslav Ne{\v s}et{\v r}il and Wormald, {Nicholas C.}",

year = "2005",

month = may,

doi = "10.1002/jgt.20064",

language = "English",

volume = "49",

pages = "69--74",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "John Wiley & Sons",

number = "1",

}

TY - JOUR

T1 - The acyclic edge chromatic number of A Random d-regular graph Is d+ 1

AU - Nešetřil, Jaroslav

AU - Wormald, Nicholas C.

PY - 2005/5

Y1 - 2005/5

N2 - 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.

AB - 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.

KW - Acyclic coloring

KW - Coloring

KW - Edge coloring

KW - Random graphs

KW - Regular graphs

UR - http://www.scopus.com/inward/record.url?scp=18744403716&partnerID=8YFLogxK

U2 - 10.1002/jgt.20064

DO - 10.1002/jgt.20064

M3 - Article

AN - SCOPUS:18744403716

SN - 0364-9024

VL - 49

SP - 69

EP - 74

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 1

ER -

The acyclic edge chromatic number of A Random d-regular graph Is d+ 1

Abstract

Keywords

Access to Document

Other files and links

Cite this