Algorithmic aspects of acyclic edge colorings

TY - JOUR

T1 - Algorithmic aspects of acyclic edge colorings

AU - Alon, N.

AU - Zaks, A.

PY - 2002

Y1 - 2002

N2 - A proper coloring of the edges of a graph G is called acyclic if there is no two-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′(G) ≥ Δ(G) + 2 where Δ(G) is the maximum degree in G. It is known that a′(G) ≤ Δ A + 2 for almost all Delta;-regular graphs, including all A-regular graphs whose girth is at least cΔ log A. We prove that determining the acyclic edge chromatic number of an arbitrary graph is an NP-complete problem. For graphs G with sufficiently large girth in terms of Δ(G), we present deterministic polynomial-time algorithms that color the edges of G acyclically using at most Δ(G) + 2 colors.

AB - A proper coloring of the edges of a graph G is called acyclic if there is no two-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′(G) ≥ Δ(G) + 2 where Δ(G) is the maximum degree in G. It is known that a′(G) ≤ Δ A + 2 for almost all Delta;-regular graphs, including all A-regular graphs whose girth is at least cΔ log A. We prove that determining the acyclic edge chromatic number of an arbitrary graph is an NP-complete problem. For graphs G with sufficiently large girth in terms of Δ(G), we present deterministic polynomial-time algorithms that color the edges of G acyclically using at most Δ(G) + 2 colors.

KW - Acyclic edge coloring

KW - Girth

UR - https://www.scopus.com/pages/publications/0141957231

UR - https://www.scopus.com/pages/publications/0141957231#tab=citedBy

U2 - 10.1007/s00453-001-0093-8

DO - 10.1007/s00453-001-0093-8

M3 - Article

SN - 0178-4617

VL - 32

SP - 611

EP - 614

JO - Algorithmica (New York)

JF - Algorithmica (New York)

IS - 4

ER -