𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The circular chromatic number of a digraph

✍ Scribed by Drago Bokal; Gas̆per Fijavz; Martin Juvan; P. Mark Kayll; Bojan Mohar

Publisher
John Wiley and Sons
Year
2004
Tongue
English
Weight
127 KB
Volume
46
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 directed k‐cycle has circular chromatic number k/(k – 1), for k ≥ 2, values of χ~c~ between 1 and 2 are possible. We show that in fact, χ~c~ takes on all rational values greater than 1. Furthermore, there exist digraphs of arbitrarily large digirth and circular chromatic number. It is NP‐complete to decide if a given digraph has χ~c~ at most 2. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 227–240, 2004

📜 SIMILAR VOLUMES

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

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

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