Paper Info
Title
Finite-dimensional T-colorings of graphs
Abstract
This article proposes finite-dimensional T - colorings on simple graphs. The ordinary T -coloring will be the one-dimensional version of our T -colorings. Let d be a positive integer and T be a set of nonnegative integers that contains 0. Denote Z 0 d ={(x 1 ,x 2 ,…,x d ) : x i ∈Z 0 , 1⩽i⩽d} , where Z 0 ={0,1,2,…} . A d - dimensional infinite-norm , ||·|| ∞ , is a function from Z 0 d to Z 0 that ||X|| ∞ = max {|x i | : 1⩽i⩽d} for X=(x 1 ,x 2 ,…,x d ) . A d - dimensional one-norm , ||·|| 1 , is a function from Z 0 d to Z 0 that ||X|| 1 =∑ i=1 d |x i | for X=(x 1 ,x 2 ,…,x d ) in Z 0 d . With these norms, we define a d - dimensional T - coloring with respect to p - norm ( p=1 or ∞ ), f , on a graph G=(V,E) as follows: f:V→Z 0 d such that ||f(u)−f(v)|| p ∉T , for all {u,v}∈E . They are denoted by T(d,p) - colorings . Note that both T -colorings for d=1 are same as usual T -colorings. The edge span of a T(d,p) -coloring f on a graph G, esp T (f;d,p) , is the maximum value of {||f(u)−f(v)|| p :{u,v}∈E(G)} . The edge span of G with respect to T(d,p) -coloring is the smallest number m such that there is a T(d,p) -coloring, f with esp T (f;d,p)=m . It is denoted by esp T (G;d,p) . We will show that the edge spans of complete graphs play important roles in seeking edge spans on general graphs. Thus, the goal of this paper is concentrated in finding edge spans of complete graphs. This is same as in the usual T -coloring problem. MSC 05C15 05C78 Keywords Norm Distance graph T-coloring Graph homomorphism References [1] J.-J. Chen, Distance graphs, Ph.D. Dissertation, Department of Applied Math, Chiao Tung University, Hsinchu, Taiwan, 1995. [2] R.B. Eggleton P. Erdős D.K. Skilton Coloring the real line J. Combin. Theory Ser. B 39 1985 86 100 [3] T.R. Jensen B. Toft Graph Coloring Problem 1995 Wiley New York [4] D.D.-F. Liu T -colorings of graphs Discrete Math. 101 1992 203 212
Year
DOI
Venue
2001
10.1016/S0304-3975(00)00249-8
Theor. Comput. Sci.
Keywords
DocType
Volume
Finite-dimensional T-colorings
Journal
263
Issue
ISSN
Citations 
1-2
Theoretical Computer Science
0
PageRank 
References 
Authors
0.34
3
1
Name
Order
Citations
PageRank
Roger K. Yeh152138.16