標題: Minimum span of no-hole (r+1)-distant colorings 作者: Chang, GJJuan, JSTLiu, 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/30039http://dx.doi.org/10.1137/S0895480198339456 ISSN: 0895-4801 DOI: 10.1137/S0895480198339456 期刊: SIAM JOURNAL ON DISCRETE MATHEMATICS Volume: 14 Issue: 3 起始頁: 370 結束頁: 380 顯示於類別： 期刊論文