✦ LIBER ✦

4-edge-coloring graphs of maximum degree 3 in linear time

✍ Scribed by San Skulrattanakulchai

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 65 KB
Volume: 81
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(01)00221-6

No coin nor oath required. For personal study only.

✦ Synopsis

We present a linear time algorithm to properly color the edges of any graph of maximum degree 3 using 4 colors. Our algorithm uses a greedy approach and utilizes a new structure theorem for such graphs.

📜 SIMILAR VOLUMES

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

Edge-face coloring of plane graphs with

Edge-face coloring of plane graphs with maximum degree nine

✍ Jean-Sébastien Sereni; Matěj Stehlík 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 189 KB 👁 1 views

An edge-face coloring of a plane graph with edge set E and face set F is a coloring of the elements of E ∪F so that adjacent or incident elements receive different colors. Borodin [Discrete Math 128(1-3): [21][22][23][24][25][26][27][28][29][30][31][32][33] 1994] proved that every plane graph of max

Equitable list-coloring for graphs of ma

Equitable list-coloring for graphs of maximum degree 3

✍ Michael J. Pelsmajer 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 102 KB

## Abstract Given lists of available colors assigned to the vertices of a graph __G__, a list coloring is a proper coloring of __G__ such that the color on each vertex is chosen from its list. If the lists all have size __k__, then a list coloring is equitable if each color appears on at most ⌈|__V

Equitable Total Coloring of Graphs with

Equitable Total Coloring of Graphs with Maximum Degree 3

✍ Wei-Fan Wang 📂 Article 📅 2002 🏛 Springer Japan 🌐 English ⚖ 120 KB

Adjacent vertex distinguishing edge-colo

Adjacent vertex distinguishing edge-colorings of graphs with smaller maximum average degree

✍ Weifan Wang; Yiqiao Wang 📂 Article 📅 2008 🏛 Springer US 🌐 English ⚖ 406 KB

An upper bound on the number of edges of

An upper bound on the number of edges of edge-coloring critical graphs with high maximum degree

✍ Lian-ying Miao; Shi-you Pang; Jian-liang Wu 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 100 KB

In this paper, we prove that any edge-coloring critical graph G with maximum degree ¿ (11 + √ 49 -24 )=2, where 6 1, has the size at least 3(|V (G)| -) + 1 if 6 7 or if ¿ 8 and |V (G)| ¿ 2 --4 -( + 6)=( -6), where is the minimum degree of G. It generalizes a result of Sanders and Zhao.