✦ LIBER ✦

Circular chromatic number of distance graphs with distance sets of cardinality 3

✍ Scribed by Xuding Zhu

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

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Suppose D is a subset of R^+^. The distance graph G(R, D) is the graph with vertex set R in which two vertices x,y are adjacent if |x−y| ∈ D. This study investigates the circular chromatic number and the fractional chromatic number of distance graphs G(R,D) with |D| = 3. As a consequence, we determine the chromatic numbers of all such distance graphs. This settles a conjecture proposed independently by Chen et al. [J. Chen, G. Chang, and K. Huang, J Graph Theory 25 (1997) 281–287 and Voigt [M. Voigt Ars Combinatoria, 52 (1999) 3–12] in the affirmative. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 195–207, 2002

📜 SIMILAR VOLUMES

Circular Chromatic Numbers of Distance G

Circular Chromatic Numbers of Distance Graphs with Distance Sets Missing Multiples

✍ Lingling Huang; Gerard J Chang 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 114 KB

Given positive integers m, k, s with m > sk, let D m,k,s represent the set {1, 2, . . . , m}\{k, 2k, . . . , sk}. The distance graph G(Z , D m,k,s ) has as vertex set all integers Z and edges connecting i and j whenever |i -j| ∈ D m,k,s . This paper investigates chromatic numbers and circular chroma

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

Fractional chromatic number and circular

Fractional chromatic number and circular chromatic number for distance graphs with large clique size

✍ Daphne Der-Fen Liu; Xuding Zhu 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 136 KB

## Abstract An Erratum has been published for this article in Journal of Graph Theory 48: 329–330, 2005. Let __M__ be a set of positive integers. The distance graph generated by __M__, denoted by __G__(__Z, M__), has the set __Z__ of all integers as the vertex set, and edges __ij__ whenever |__i__

D. Liu and X. Zhu, Erratum to: “Fraction

D. Liu and X. Zhu, Erratum to: “Fractional chromatic number and circular chromatic number for distance graphs with large clique size”. Journal of Graph Theory47(2) 2004, 129–146

✍ Daphne Der-Fen Liu; Xuding Zhu 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 45 KB

## Abstract The original article to which this Erratum refers was published in Journal of Graph Theory 47:129–146,2004.

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)