✦ LIBER ✦

Girth and fractional chromatic number of planar graphs

✍ Scribed by Amir Pirnazar; Daniel H. Ullman

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

No coin nor oath required. For personal study only.

✦ Synopsis

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 fractional chromatic number of a planar graph with that girth, and we provide upper and lower bounds for this quantity. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 201–217, 2002; DOI 10.1002/jgt10024

📜 SIMILAR VOLUMES

Group chromatic number of planar graphs

Group chromatic number of planar graphs of girth at least 4

✍ Hong-Jian Lai; Xiangwen Li 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 212 KB 👁 1 views

## 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 lea

Circular Chromatic Numbers and Fractiona

Circular Chromatic Numbers and Fractional Chromatic Numbers of Distance Graphs

✍ G.J. Chang; L. Huang; X. Zhu 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 171 KB

This paper studies circular chromatic numbers and fractional chromatic numbers of distance graphs G(Z , D) for various distance sets D. In particular, we determine these numbers for those D sets of size two, for some special D sets of size three, for

The fractional chromatic number of infin

The fractional chromatic number of infinite graphs

✍ Imre Leader 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 398 KB 👁 1 views

## Abstract The fractional chromatic number of a graph __G__ is the infimum of the total weight that can be assigned to the independent sets of __G__ in such a way that, for each vertex __v__ of __G__, the sum of the weights of the independent sets containing __v__ is at least 1. In this note we g

The fractional chromatic number of mycie

The fractional chromatic number of mycielski's graphs

✍ Michael Larsen; James Propp; Daniel Ullman 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 236 KB

The most familiar construction of graphs whose clique number is much smaller than their chromatic number is due to Mycielski, who constructed a sequence G, of triangle-free graphs with ,y(G,) = n. In this article, w e calculate the fractional chromatic number of G, and show that this sequence of num

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