✦ LIBER ✦

(2 + ?)-Coloring of planar graphs with large odd-girth

✍ Scribed by Klostermeyer, William; Zhang, Cun Quan

Publisher: John Wiley and Sons
Year: 2000
Tongue: English
Weight: 258 KB
Volume: 33
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(200002)33:2<109::aid-jgt5>3.0.co;2-f

No coin nor oath required. For personal study only.

✦ Synopsis

The odd-girth of a graph is the length of a shortest odd circuit. A conjecture by Pavol Hell about circular coloring is solved in this article by showing that there is a function f ( ) for each : 0 < < 1 such that, if the odd-girth of a planar graph G is at least f ( ), then G is (2 + )-colorable. Note that the function f ( ) is independent of the graph G and → 0 if and only if f ( ) → ∞. A key lemma, called the folding lemma, is proved that provides a reduction method, which maintains the odd-girth of planar graphs. This lemma is expected to have applications in related problems.

📜 SIMILAR VOLUMES

UniquelyH-colorable graphs with large gi

UniquelyH-colorable graphs with large girth

✍ Zhu, Xuding 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 498 KB 👁 1 views

Suppose G and H are graphs. We say G is H-colorable if there is a homomorphism (edge-preserving vertex mapping) from G to H. We say a graph G is uniquely H-colorable if there is an onto homomorphism c from G to H, and any other homomorphism from G to H is the composition o o c of c with an automorph

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 👁 2 views

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

The circular chromatic number of series-

The circular chromatic number of series-parallel graphs with large girth

✍ Chien, Chihyun; Zhu, Xuding 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 1 views

It was proved by Hell and Zhu that, if G is a series-parallel graph of girth at least 2 (3k -1)/2 , then χ c (G) ≤ 4k/(2k -1). In this article, we prove that the girth requirement is sharp, i.e., for any k ≥ 2, there is a series-parallel graph G of girth 2 (3k -1)/2 -1 such that χ c (G) > 4k/(2k -1)