✦ LIBER ✦

Circular chromatic number of subgraphs

✍ Scribed by Hossein Hajiabolhassan; Xuding Zhu

Publisher: John Wiley and Sons
Year: 2003
Tongue: English
Weight: 107 KB
Volume: 44
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10127

No coin nor oath required. For personal study only.

✦ Synopsis

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 exists an integer g such that if G has girth at least g and $\chi _c (G) = k/d$ then for every vertex v of G, $\chi _c (G-{v})> k/d - \varepsilon $. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 95–105, 2003

📜 SIMILAR VOLUMES

Subgraphs of large connectivity and chro

Subgraphs of large connectivity and chromatic number in graphs of large chromatic number

✍ N. Alon; D. Kleitman; C. Thomassen; M. Saks; P. Seymour 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB

For each pair k, rn of natural numbers there exists a natural number f(k, rn) such that every f ( k , m)-chromatic graph contains a k-connected subgraph of chromatic number at least rn.

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 number and Mycielski

Circular chromatic number and Mycielski construction

✍ Hossein Hajiabolhassan; Xuding Zhu 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 94 KB

## Abstract This paper gives a sufficient condition for a graph __G__ to have its circular chromatic number equal to its chromatic number. By using this result, we prove that for any integer __t__ ≥ 1, there exists an integer __n__ such that for all $k \ge n, \chi \_c (M^t(K\_k))\,= \chi(M^t(K\_k))

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