✦ LIBER ✦

Circular chromatic numbers of some reduced Kneser graphs

✍ Scribed by Ko-Wei Lih; Daphne Der-Fen Liu

Publisher: John Wiley and Sons
Year: 2002
Tongue: English
Weight: 75 KB
Volume: 41
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10052

No coin nor oath required. For personal study only.

✦ Synopsis

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 of KG~2~(m,2) is equal to m−2, its ordinary chromatic number. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 62–68, 2002

📜 SIMILAR VOLUMES

Multichromatic numbers, star chromatic n

Multichromatic numbers, star chromatic numbers and Kneser graphs

✍ Johnson, A.; Holroyd, F. C.; Stahl, S. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB 👁 1 views

We investigate the relation between the multichromatic number (discussed by Stahl and by Hilton, Rado and Scott) and the star chromatic number (introduced by Vince) of a graph. Denoting these by χ \* and η \* , the work of the above authors shows that χ \* (G) = η \* (G) if G is bipartite, an odd cy

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 chromatic number of the general K

On the chromatic number of the general Kneser-graph

✍ P. Frankl 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 1 views

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

Star chromatic numbers of some planar gr

Star chromatic numbers of some planar graphs

✍ Gao, Guogang; Wang, Yiju; Zhou, Huishan 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 173 KB 👁 2 views

The concept of the star chromatic number of a graph was introduced by Vince (A. Vince, Star chromatic number, J. Graph Theory 12 (1988), 551--559), which is a natural generalization of the chromatic number of a graph. This paper calculates the star chromatic numbers of three infinite families of pla

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