Browsing by Author "Liu, DDF"

Now showing 1 - 4 of 4

Distance graphs and T-coloring
(1999-03-01)
Chang, GJ
;
Liu, DDF
;
Zhu, XD
;
應用數學系
;
Department of Applied Mathematics
We discuss relationships among T-colorings of graphs and chromatic numbers, fractional chromatic numbers, and circular chromatic numbers of distance graphs. We first prove that for any finite integral set T that contains 0, the asymptotic T-coloring ratio R(T) is equal to the fractional chromatic number of the distance graph G(Z, D), where D = T-{0}. This fact is then used to study the distance graphs with distance sets of the form D-m,D- k = {1, 2, ..., m}- {k}. The chromatic numbers and the fractional chromatic numbers of G(Z, D-m,D- k) are determined for all values of m and k. Furthermore, circular chromatic numbers of G(Z, D-m,D- k) fur some special values of m and k are obtained. (C) 1999 Academic Press.
Minimum span of no-hole (r+1)-distant colorings
(2001)
Chang, GJ
;
Juan, JST
;
Liu, DDF
;
應用數學系
;
Department of Applied Mathematics
Given a nonnegative integer r, a no-hole (r + 1)-distant coloring, called N-r-coloring, of a graph G is a function that assigns a nonnegative integer (color) to each vertex such that the separation of the colors of any pair of adjacent vertices is greater than r, and the set of the colors used must be consecutive. Given r and G, the minimum N-r-span of G, nsp(r)(G), is the minimum difference of the largest and the smallest colors used in an N-r-coloring of G if there exists one; otherwise, define nsp,(G) = infinity. The values of nsp(1)(G) (r = 1) for bipartite graphs are given by Roberts [Math. Comput. Modelling, 17 (1993), pp. 139-144]. Given r greater than or equal to 2, we determine the values of nsp(r)(G) for all bipartite graph with at least r - 2 isolated vertices. This leads to complete solutions of nsp(2)(G) for bipartite graphs.
No-hole 2-distant colorings for unit interval graphs
(2001-10-01)
Chang, GJ
;
Juan, ST
;
Liu, DDF
;
應用數學系
;
Department of Applied Mathematics
Given a graph, a no-hole 2-distant coloring (also called N-coloring) is a function f that assigns to each vertex a non-negative integer (color) such that the separation of the colors of any pair of adjacent vertices must be at least 2, and all the colors used by f form a consecutive set (the no-hole assumption). The minimum consecutive N-span of G, csp(1)(G), is the minimum difference of the largest and the smallest colors used in an N-coloring of G, if there exists such a coloring; otherwise, define csp(1)(G) = infinity. Here we investigate the exact values of csp(1)(G) for unit interval graphs (also known as 1-unit sphere graphs). Earlier results by Roberts [18] indicate that if G is a unit interval graph on n vertices, then csp(1) (G) is either 2 chi (G) - 1 or 2 chi (G) - 2, if n > 2 chi (G) - 1; csp(1)(G) = infinity, if n < 2(G) - 1, where chi (G) denotes the chromatic number. We show that in the former case (when n > 2 chi (G) - 1), both values of csp(1)(G) are attained, and give several families of unit interval graphs such that csp(1)(G) = 2 chi (G) - 2. In addition, the exact values of csp(1)(G) are completely determined for unit interval graphs with chi (G) = 3.
On L(d, 1)-labelings of graphs
(2000-06-06)
Chang, GJ
;
Ke, WT
;
Kuo, D
;
Liu, DDF
;
Yeh, RK
Given a graph G and a positive integer d, an L(d, 1)-labeling of G is a function f that assigns to each vertex of G a non-negative integer such that if two vertices u and u are adjacent, then f(u) - f(v) greater than or equal to d; if u and v are not adjacent but there is a two-edge path between them, then f(u)- f(v) greater than or equal to 1. The L(d, 1)-number of G, lambda(d)(G), is defined as the minimum m such that there is an L(d, 1)-labeling f of G with f(V) subset of or equal to {0, 1, 2,,.., m}. Motivated by the channel assignment problem introduced by Hale (Proc, IEEE 68 (1980) 1497-1514), the L(2, 1)-labeling and the L(1, 1)-labeling (as d = 2 and 1, respectively) have been studied extensively in the past decade. This article extends the study to all positive integers d. We prove that lambda(d)(G) less than or equal to Delta(2) + (d - 1)Delta for any graph G with maximum degree d. Different lower and upper bounds of lambda(d)(G) for some families of graphs including trees and chordal graphs are presented. In particular, we show that the lower and the upper bounds for trees are both attainable, and the upper bound for chordal graphs can be improved for several subclasses of chordal graphs. (C) 2000 Elsevier Science B,V. All rights reserved.