✦ LIBER ✦

Coloring the square of a planar graph

✍ Scribed by Jan van den Heuvel; Sean McGuinness

Publisher: John Wiley and Sons
Year: 2003
Tongue: English
Weight: 125 KB
Volume: 42
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10077

No coin nor oath required. For personal study only.

✦ Synopsis

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 Wiley Periodicals, Inc. J Graph Theory 42: 110–124, 2003

📜 SIMILAR VOLUMES

List-coloring the square of a subcubic g

List-coloring the square of a subcubic graph

✍ Daniel W. Cranston; Seog-Jin Kim 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 266 KB

## Abstract The __square__ __G__^2^ of a graph __G__ is the graph with the same vertex set __G__ and with two vertices adjacent if their distance in __G__ is at most 2. Thomassen showed that every planar graph __G__ with maximum degree Δ(__G__) = 3 satisfies χ(__G__^2^) ≤ 7. Kostochka and Woodall c

Extending colorings of locally planar gr

Extending colorings of locally planar graphs

✍ Michael O. Albertson; Joan P. Hutchinson 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB 👁 1 views

Suppose G is a graph embedded in S g with width (also known as edge width) at least 264(2 g À 1). If P V(G) is such that the distance between any two vertices in P is at least 16, then any 5-coloring of P extends to a 5-coloring of all of G. We present similar extension theorems for 6-and 7-chromati

Adapted list coloring of planar graphs

✍ Louis Esperet; Mickaël Montassier; Xuding Zhu 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB

## Abstract Given an edge coloring __F__ of a graph __G__, a vertex coloring of __G__ is __adapted to F__ if no color appears at the same time on an edge and on its two endpoints. If for some integer __k__, a graph __G__ is such that given any list assignment __L__ to the vertices of __G__, with |_

Acyclic list 7-coloring of planar graphs

✍ O. V. Borodin; D. G. Fon-Der Flaass; A. V. Kostochka; A. Raspaud; E. Sopena 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 83 KB

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

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

Total colorings of planar graphs with la

Total colorings of planar graphs with large maximum degree

✍ Borodin, O. V.; Kostochka, A. V.; Woodall, D. R. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 97 KB 👁 3 views

It is proved that a planar graph with maximum degree ∆ ≥ 11 has total (vertex-edge) chromatic number ∆ + 1.