✦ LIBER ✦

Density of the circular chromatic numbers of series-parallel graphs

✍ Scribed by Zhishi Pan; Xuding Zhu

Publisher: John Wiley and Sons
Year: 2004
Tongue: English
Weight: 120 KB
Volume: 46
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10171

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Suppose G is a series‐parallel graph. It was proved in 3 that either ~χ__c__~(G) = 3 or ~χ__c__~(G) ≤ 8/3. So none of the rationals in the interval (8/3, 3) is the circular chromatic number of a series‐parallel graph. This paper proves that for every rational r ∈ [2, 8/3] ∪ {3} there exists a series‐parallel graph G with ~χ__c__~(G) = r. © 2004 Wiley Periodicals, Inc. J Graph Theory 46:57–68, 2004

📜 SIMILAR VOLUMES

The circular chromatic number of series-

The circular chromatic number of series-parallel graphs

✍ Hell, Pavol; Zhu, Xuding 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 238 KB 👁 2 views

In this article, we consider the circular chromatic number χ c (G) of series-parallel graphs G. It is well known that series-parallel graphs have chromatic number at most 3. Hence, their circular chromatic numbers are at most 3. If a seriesparallel graph G contains a triangle, then both the chromati

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)

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

On the circular chromatic number of circ

On the circular chromatic number of circular partitionable graphs

✍ Arnaud Pêcher; Xuding Zhu 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB

## Abstract This article studies the circular chromatic number of a class of circular partitionable graphs. We prove that an infinite family of circular partitionable graphs __G__ has $\chi\_ c (G) = \chi(G)$. A consequence of this result is that we obtain an infinite family of graphs __G__ with th

Circular chromatic numbers of some reduc

Circular chromatic numbers of some reduced Kneser graphs

✍ Ko-Wei Lih; Daphne Der-Fen Liu 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 75 KB

## Abstract The vertex set of the reduced Kneser graph KG~2~(__m,2__) consists of all pairs {__a,b__} such that __a, b__ε{1,2,…,__m__} and 2≤|__a__−__b__|≤__m__−2. Two vertices are defined to be adjacent if they are disjoint. We prove that, if __m__≥4 __and m__≠5, then the circular chromatic number

The circular chromatic numbers of planar

The circular chromatic numbers of planar digraphs

✍ Chin-Ann Soh 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 162 KB 👁 1 views

## Abstract The circular chromatic number is a refinement of the chromatic number of a graph. It has been established in [3,6,7] that there exists planar graphs with circular chromatic number __r__ if and only if __r__ is a rational in the set {1} ∪ [2,4]. Recently, Mohar, in [1,2] has extended the