𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The Two-Coloring Number and Degenerate Colorings of Planar Graphs

✍ Scribed by Kierstead, Hal; Mohar, Bojan; Špacapan, Simon; Yang, Daqing; Zhu, Xuding

Book ID
118197703
Publisher
Society for Industrial and Applied Mathematics
Year
2009
Tongue
English
Weight
284 KB
Volume
23
Category
Article
ISSN
0895-4801

No coin nor oath required. For personal study only.

📜 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

Edge-partitions of planar graphs and the
Edge-partitions of planar graphs and their game coloring numbers
✍ Wenjie He; Xiaoling Hou; Ko-Wei Lih; Jiating Shao; Weifan Wang; Xuding Zhu 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 98 KB 👁 1 views

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 n

Coloring the square of a planar graph
Coloring the square of a planar graph
✍ Jan van den Heuvel; Sean McGuinness 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB 👁 2 views

## Abstract We prove that for any planar graph __G__ with maximum degree Δ, it holds that the chromatic number of the square of __G__ satisfies χ(__G__^2^) ≤ 2Δ + 25. We generalize this result to integer labelings of planar graphs involving constraints on distances one and two in the graph. © 2002