標題: Minimum span of no-hole (r+1)-distant colorings
作者: Chang, GJ
Juan, JST
Liu, DDF
應用數學系
Department of Applied Mathematics
關鍵字: vertex-coloring;no-hole (r plus l)-distant coloring;minimum span;bipartite graphs
公開日期: 2001
摘要: 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.
URI: http://hdl.handle.net/11536/30039
http://dx.doi.org/10.1137/S0895480198339456
ISSN: 0895-4801
DOI: 10.1137/S0895480198339456
期刊: SIAM JOURNAL ON DISCRETE MATHEMATICS
Volume: 14
Issue: 3
起始頁: 370
結束頁: 380
顯示於類別:期刊論文


文件中的檔案:

  1. 000171372500008.pdf