Please wait a minute...
Frontiers of Mathematics in China

ISSN 1673-3452

ISSN 1673-3576(Online)

CN 11-5739/O1

Postal Subscription Code 80-964

2018 Impact Factor: 0.565

Front Math Chin    2009, Vol. 4 Issue (2) : 325-334    https://doi.org/10.1007/s11464-009-0014-8
RESEARCH ARTICLE
On vertex-coloring edge-weighting of graphs
Hongliang LU1, Xu YANG1, Qinglin YU1,2()
1. Center for Combinatorics, Key Laboratory of Pure Mathematics and Combinatorics, Ministry of Education of China, Nankai University, Tianjin 300071, China; 2. Department of Mathematics and Statistics, Thompson Rivers University, Kamloops, BC, V2C 5N3, Canada
 Download: PDF(162 KB)   HTML
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Abstract

A k-edge-weightingw of a graph G is an assignment of an integer weight, w(e) ∈ {1, …, k}, to each edge e. An edge-weighting naturally induces a vertex coloring c by de?ning for every uV (G). A k-edge-weighting of a graph G is vertex-coloring if the induced coloring c is proper, i.e., c(u) ≠ c(v) for any edge uvE(G). When k ≡ 2 (mod 4) and k≥6, we prove that if G is k-colorable and 2-connected, δ(G)≥k - 1, then G admits a vertex-coloring k-edge-weighting. We also obtain several suffcient conditions for graphs to be vertex-coloring k-edge-weighting.

Keywords Vertex coloring      edge-weighting     
Corresponding Author(s): YU Qinglin,Email:yu@tru.ca   
Issue Date: 05 June 2009
 Cite this article:   
Hongliang LU,Xu YANG,Qinglin YU. On vertex-coloring edge-weighting of graphs[J]. Front Math Chin, 2009, 4(2): 325-334.
 URL:  
https://academic.hep.com.cn/fmc/EN/10.1007/s11464-009-0014-8
https://academic.hep.com.cn/fmc/EN/Y2009/V4/I2/325
1 Addario-Berry L, Aldred R E L, Dalal K, Reed B A. Vertex coloring edge partitions. J Combin Theory, Ser B , 2005, 94: 237-244
doi: 10.1016/j.jctb.2005.01.001
2 Balister P N, Riordan O M, Schelp R H. Vertex-distinguishing edge colorings of graphs. J Graph Theory , 2003, 42: 95-109
doi: 10.1002/jgt.10076
3 Bollobás B. Modern Graph Theory. 2nd Ed. New York: Springer-Verlag, 1998
4 Karónski M, Luczak T, Thomason A. Edge weights and vertex colors. J Combin Theory, Ser B , 2004, 91: 151-157
doi: 10.1016/j.jctb.2003.12.001
5 Wang T, Yu Q. On vertex-coloring 13-edge-weighting. Front Math China , 2008, 3(4): 581-587
doi: 10.1007/s11464-008-0041-x
[1] WANG Tao, YU Qinglin. On vertex-coloring 13-edge-weighting[J]. Front. Math. China, 2008, 3(4): 581-587.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed