✦ LIBER ✦

Group chromatic number of planar graphs of girth at least 4

✍ Scribed by Hong-Jian Lai; Xiangwen Li

Publisher: John Wiley and Sons
Year: 2006
Tongue: English
Weight: 212 KB
Volume: 52
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20147

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Jeager et al. introduced a concept of group connectivity as a generalization of nowhere zero flows and its dual concept group coloring, and conjectured that every 5‐edge connected graph is Z~3~‐connected. For planar graphs, this is equivalent to that every planar graph with girth at least 5 must have group chromatic number at most 3. In this article, we show that if G is a plane graph with girth at least 4 such that all 4 cycles are independent, every 4‐cycle is a facial cycle and the distance between every pair of a 4‐cycle and a 5‐cycle is at least 1, then the group chromatic number of G is at most 3. As a special case, we show that the conjecture above holds for planar graphs. We also prove that if G is a connected K~3,3~‐minor free graph with girth at least 5, then the group chromatic number is at most 3. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 51–72, 2006

📜 SIMILAR VOLUMES

Girth and fractional chromatic number of

Girth and fractional chromatic number of planar graphs

✍ Amir Pirnazar; Daniel H. Ullman 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB 👁 1 views

## Abstract In 1959, even before the Four‐Color Theorem was proved, Grötzsch showed that planar graphs with girth at least 4 have chromatic number at the most 3. We examine the fractional analogue of this theorem and its generalizations. For any fixed girth, we ask for the largest possible fraction

The star-chromatic number of planar grap

The star-chromatic number of planar graphs

✍ Moser, David 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB 👁 2 views

The star-chromatic number of a graph, a parameter introduced by Vince, is a natural generalization of the chromatic number of a graph. Here we construct planar graphs with star-chromatic number r, where r is any rational number between 2 and 3, partially answering a question of Vince.

Star chromatic numbers of some planar gr

Star chromatic numbers of some planar graphs

✍ Gao, Guogang; Wang, Yiju; Zhou, Huishan 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 173 KB 👁 2 views

The concept of the star chromatic number of a graph was introduced by Vince (A. Vince, Star chromatic number, J. Graph Theory 12 (1988), 551--559), which is a natural generalization of the chromatic number of a graph. This paper calculates the star chromatic numbers of three infinite families of pla

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

On the vertex face total chromatic numbe

On the vertex face total chromatic number of planar graphs

✍ Weifan, Wang; Jiazhuang, Liu 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 471 KB 👁 2 views

Let G be a planar graph. The vertex face total chromatic number ,y13(G) of G is the least number of colors assigned to V(G) U F(G) such that no adjacent or incident elements receive the same color. The main results of this paper are as follows: (1) We give the vertex face total chromatic number for

Total chromatic number of planar graphs

Total chromatic number of planar graphs with maximum degree ten

✍ Weifan Wang 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 161 KB 👁 1 views