✦ LIBER ✦

The circular chromatic number of the Mycielskian ofGdk

✍ Scribed by Huang, Lingling; Chang, Gerard J.

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 125 KB
Volume: 32
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199909)32:1<63::aid-jgt6>3.0.co;2-b

No coin nor oath required. For personal study only.

✦ Synopsis

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, and Zhu [G. J. Chang, L. Huang, & X. Zhu, Discrete Math, to appear] have investigated circular chromatic numbers of Mycielskians for several classes of graphs. In this article, we study circular chromatic numbers of Mycielskians for another class of graphs G d k . The main result is that χ c (µ(G d k )) = χ(µ(G d k )), which settles a problem raised in [G. J. Chang, L. Huang, & X. Zhu, Discrete Math, to appear, and X. Zhu, to appear]. As χ c (G d k ) = k d and χ(G d k ) = k d , consequently, there exist graphs G such that χ c (G) is as close to χ(G) -1 as you want, but χ c (µ(G)) = χ(µ(G)).

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

The chromatic number of oriented graphs

✍ Sopena, Eric 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB 👁 2 views

We introduce in this paper the notion of the chromatic number of an oriented graph G (that is of an antisymmetric directed graph) defined as the minimum order of an oriented graph H such that G admits a homomorphism to H. We study the chromatic number of oriented k-trees and of oriented graphs with

The chromatic numbers of random hypergra

The chromatic numbers of random hypergraphs

✍ Michael Krivelevich; Benny Sudakov 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 261 KB

For a pair of integers 1 F ␥r, the ␥-chromatic number of an r-uniform Ž . hypergraph H s V, E is the minimal k, for which there exists a partition of V into subsets < < T, . . . , T such that e l T F ␥ for every e g E. In this paper we determine the asymptotic 1 k i Ž . behavior of the ␥-chromatic n

The round-up property of the fractional

The round-up property of the fractional chromatic number for proper circular arc graphs

✍ Niessen, Thomas; Kind, Jaakob 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB 👁 2 views

Let G = (V, E) be a graph and let k be a nonnegative integer. A vector c ∈ Z V + is called k-colorable iff there exists a coloring of G with k colors that assigns exactly c(v) colors to vertex v ∈ V . Denote by χ(G) and χ f (G) the chromatic number and fractional chromatic number, respectively. We p

On the chromatic number of disk graphs

✍ Malesi?ska, Ewa; Piskorz, Steffen; Wei�enfels, Gerhard 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 172 KB 👁 2 views

Colorings of disk graphs arise in the study of the frequency-assignment problem in broadcast networks. Motivated by the observations that the chromatic number of graphs modeling real networks hardly exceeds their clique number, we examine the related properties of the unit disk (UD) graphs and their