Browsing by Author "Huang, LL"

Now showing 1 - 5 of 5

Circular chromatic numbers and fractional chromatic numbers of distance graphs
(1998-05-01)
Chang, GJ
;
Huang, LL
;
Zhu, XD
;
應用數學系
;
Department of Applied Mathematics
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 D = {1, 2,..., m, n} with 1 less than or equal to m < n, for D = {q, q + 1,..., p} with q less than or equal to p, and for D = {1, 2,..., m} - {k} with 1 less than or equal to k less than or equal to m. (C) 1998 Academic Press.
Circular chromatic numbers of distance graphs with distance sets missing multiples
(2000-02-01)
Huang, LL
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
Given positive integers m, k, s with m > sk, let D-m,D-k,D-s represent the set {1, 2,..., m} {k, 2k,..., sk}. The distance graph G(Z, D-m,D-k,D-s) has as vertex set all integers Z and edges connecting i and j whenever i - j is an element of D-m,D-k,D-s. This paper investigates chromatic numbers and circular chromatic numbers of the distance graphs G(Z, D-m,D-k,D-s). Deuber and Zhu [8] and Liu [13] have shown that [m+sk+1/s+1] less than or equal to chi(G(Z, D-m,D-k,D-s)) less than or equal to [m+sk+1/s+1] + 1 when m greater than or equal to (s + 1)k. In this paper, by establishing bounds for the circular chromatic number chi(C)(G(Z, D-m,D-k,D-s)) of G(Z, D-m,D-k,D-s), we determine the values of chi(G(Z, D-m,D-k,D-s)) for all positive integers m, k, s and chi(C)(G(Z, D-m,D-k,D-s)) for some positive integers m, k, s. (C) 2000 Academic Press.
Circular chromatic numbers of Mycielski's graphs
(1999-07-28)
Chang, GJ
;
Huang, LL
;
Zhu, XD
;
應用數學系
;
Department of Applied Mathematics
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.
Sortabilities of partition properties
(1999)
Chang, GJ
;
Chen, FL
;
Huang, LL
;
Hwang, FK
;
Nuan, ST
Consider the partition of a set of integers into parts. Various partition properties have been proposed in the literature to facilitate the restriction of the focus of attention to some small class of partitions. Recently, Hwang, Rothblum and Yao defined and studied the sortability of these partition properties as a tool to prove the existence of a partition with such a property in a given family. In this paper we determine the sortability indices of the seven most interesting properties of partitions providing a complete solution to the sortability issue.
The circular chromatic number of the Mycielskian of G(k)(d)
(1999-09-01)
Huang, LL
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
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. 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(k)(d). The main result is that chi(c)(mu(G(k)(d))) = chi(mu(G(k)(d))), which settles a problem raised in [G. J. Chang, L. Huang, & X. Zhu, Discrete Math, to appear, and X. Zhu, to appear]. As chi(c)(G(k)(d)) = k/d and chi(G(k)(d)) = [k/d], consequently, there exist graphs G such that chi(c)(G) is as close to chi(G) - 1 as you want, but chi(c)(mu(G)) = chi(mu(G)). (C) 1999 John Wiley & Sons, Inc.