✦ LIBER ✦

Edge-partitions of planar graphs and their game coloring numbers

✍ Scribed by Wenjie He; Xiaoling Hou; Ko-Wei Lih; Jiating Shao; Weifan Wang; Xuding Zhu

Publisher: John Wiley and Sons
Year: 2002
Tongue: English
Weight: 98 KB
Volume: 41
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10069

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a planar graph and let g(G) and Á(G) be its girth and maximum degree, respectively. We show that G has an edge-partition into a forest and a subgraph H so that (i)

-cycles (though it may contain 3-cycles). These results are applied to find the following upper bounds for the game coloring number col g (G) of a planar graph G:

11 if G does not contain 4-cycles (though it may contain 3-cycles).

📜 SIMILAR VOLUMES

The Game Coloring Number of Planar Graph

The Game Coloring Number of Planar Graphs

✍ Xuding Zhu 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 121 KB

This paper discusses a variation of the game chromatic number of a graph: the game coloring number. This parameter provides an upper bound for the game chromatic number of a graph. We show that the game coloring number of a planar graph is at most 19. This implies that the game chromatic number of a

Acyclic edge coloring of triangle-free p

Acyclic edge coloring of triangle-free planar graphs

✍ Manu Basavaraju; L. Sunil Chandran 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 233 KB 👁 2 views

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 conjectured by Al

NP-completeness of list coloring and pre

NP-completeness of list coloring and precoloring extension on the edges of planar graphs

✍ Dániel Marx 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 110 KB

## Abstract In the edge precoloring extension problem, we are given a graph with some of the edges having preassigned colors and it has to be decided whether this coloring can be extended to a proper __k__‐edge‐coloring of the graph. In list edge coloring every edge has a list of admissible colors,