𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the circular chromatic number of circular partitionable graphs

✍ Scribed by Arnaud Pêcher; Xuding Zhu

Publisher
John Wiley and Sons
Year
2006
Tongue
English
Weight
168 KB
Volume
52
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 the rare property that the deletion of each vertex decreases its circular chromatic number by exactly 1. © 2006 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

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

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

Density of the circular chromatic number
Density of the circular chromatic numbers of series-parallel graphs
✍ Zhishi Pan; Xuding Zhu 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 120 KB 👁 1 views

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

On the complexity of the circular chroma
On the complexity of the circular chromatic number
✍ H. Hatami; R. Tusserkani 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 71 KB 👁 1 views

## Abstract Circular chromatic number, χ~__c__~ is a natural generalization of chromatic number. It is known that it is **NP**‐hard to determine whether or not an arbitrary graph __G__ satisfies χ(__G__)=χ~__c__~(__G__). In this paper we prove that this problem is **NP**‐hard even if the chromatic

Circular chromatic number of subgraphs
Circular chromatic number of subgraphs
✍ Hossein Hajiabolhassan; Xuding Zhu 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 107 KB

## Abstract This paper proves that every (__n__ + )‐chromatic graph contains a subgraph __H__ with $\chi \_c (H) = n$. This provides an easy method for constructing sparse graphs __G__ with $\chi\_c (G) = \chi ( G) = n$. It is also proved that for any ε > 0, for any fraction __k/d__ > 2, there exis