✦ LIBER ✦

Acyclic edge chromatic number of outerplanar graphs

✍ Scribed by Jian-Feng Hou; Jian-Liang Wu; Gui-Zhen Liu; Bin Liu

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

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A proper edge coloring 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 χ(G), is the least number of colors in an acyclic edge coloring of G. In this paper, we determine completely the acyclic edge chromatic number of outerplanar graphs. The proof is constructive and supplies a polynomial time algorithm to acyclically color the edges of any outerplanar graph G using χ(G) colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 22–36, 2010

📜 SIMILAR VOLUMES

Game chromatic number of outerplanar gra

Game chromatic number of outerplanar graphs

✍ Guan, D. J.; Zhu, Xuding 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 172 KB 👁 2 views

This note proves that the game chromatic number of an outerplanar graph is at most 7. This improves the previous known upper bound of the game chromatic number of outerplanar graphs.

The relaxed game chromatic number of out

The relaxed game chromatic number of outerplanar graphs

✍ Charles Dunn; Hal A. Kierstead 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 92 KB

## Abstract The (__r__,__d__)‐relaxed coloring game is played by two players, Alice and Bob, on a graph __G__ with a set of __r__ colors. The players take turns coloring uncolored vertices with legal colors. A color α is legal for an uncolored vertex __u__ if __u__ is adjacent to at most __d__ vert

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

Edge-face chromatic number and edge chro

Edge-face chromatic number and edge chromatic number of simple plane graphs

✍ Rong Luo; Cun-Quan Zhang 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB

## Abstract Given a simple plane graph __G__, an edge‐face __k__‐coloring of __G__ is a function ϕ : __E__(__G__) ∪ __F__(G) → {1,…,__k__} such that, for any two adjacent or incident elements __a__, __b__ ∈ __E__(__G__) ∪ __F__(__G__), ϕ(__a__) ≠ ϕ(__b__). Let χ~e~(__G__), χ~ef~(__G__), and Δ(__G_

Acyclic and oriented chromatic numbers o

Acyclic and oriented chromatic numbers of graphs

✍ Kostochka, A. V.; Sopena, E.; Zhu, X. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 121 KB 👁 2 views

The oriented chromatic number χ o ( G) of an oriented graph G = (V, A) is the minimum number of vertices in an oriented graph H for which there exists a homomorphism of G to H. The oriented chromatic number χ o (G) of an undirected graph G is the maximum of the oriented chromatic numbers of all the

The acyclic edge chromatic number of a r

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

✍ Jaroslav Nešetřil; Nicholas C. Wormald 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 67 KB 👁 1 views

## 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 a