✦ LIBER ✦

On the complexity of the circular chromatic number

✍ Scribed by H. Hatami; R. Tusserkani

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

No coin nor oath required. For personal study only.

✦ Synopsis

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 number of the graph is known. This answers a question of Xuding Zhu. Also we prove that for all positive integers k ≥ 2 and n ≥ 3, for a given graph G with χ(G) = n, it is NP‐complete to verify if $\chi _c(G) \le n- {1\over k}$. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 226–230, 2004

📜 SIMILAR VOLUMES

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

The circular chromatic number of a digra

The circular chromatic number of a digraph

✍ Drago Bokal; Gas̆per Fijavz; Martin Juvan; P. Mark Kayll; Bojan Mohar 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB 👁 1 views

## Abstract We introduce the circular chromatic number χ~__c__~ of a digraph and establish various basic results. They show that the coloring theory for digraphs is similar to the coloring theory for undirected graphs when independent sets of vertices are replaced by acyclic sets. Since the directe

The circular chromatic number of the Myc

The circular chromatic number of the Mycielskian ofGdk

✍ Huang, Lingling; Chang, Gerard J. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB 👁 2 views

In a search for triangle-free graphs with arbitrarily large chromatic numbers, Mycielski developed a graph transformation that transforms a graph G into a new graph µ(G), we now call the Mycielskian of G, which has the same clique number as G and whose chromatic number equals χ(G)+1. Chang, Huang, a

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

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

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