標題: Circular chromatic numbers of Mycielski's graphs
作者: Chang, GJ
Huang, LL
Zhu, XD
應用數學系
Department of Applied Mathematics
關鍵字: circular chromatic number;Mycielski's graphs;girth;homomorphism;connectivity;critical graph
公開日期: 28-Jul-1999
摘要: 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 mu(G), we now call the Mycielskian of G, which has the same clique number as G and whose chromatic number equals chi(G) + 1. Let mu(n)(G) = mu(mu(n-1)(G)) for n greater than or equal to 2. This paper investigates the circular chromatic numbers of Mycielski's graphs. In particular, the following results are proved in this paper: (1) for any graph G of chromatic number n, chi(c)(mu(n-1)(G)) less than or equal to chi(mu(n-1)(G)) - 1/2; (2) if a graph G satisfies chi(c)(G) less than or equal to chi(G) - 1/d with d = 2 or 3, then chi(c)(mu(2)(G)) less than or equal to chi(mu(2)(G)) - 1/d; (3) for any graph G of chromatic number 3, chi(c)(mu(G)) = chi(mu(G)) = 4; (4) chi(c)(mu(K-n)) = chi(mu(K-n)) = n + 1 for n greater than or equal to 3 and chi(c)(mu(2)(K-n)) = chi(mu(2)(K-n)) = n + 2 for n greater than or equal to 4. (C) 1999 Elsevier Science B.V. All rights reserved.
URI: http://hdl.handle.net/11536/31196
ISSN: 0012-365X
期刊: DISCRETE MATHEMATICS
Volume: 205
Issue: 1-3
起始頁: 23
結束頁: 37
Appears in Collections:Articles


Files in This Item:

  1. 000081625300002.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.