RESEARCH ARTICLE

On vertex-coloring edge-weighting of graphs

  • Hongliang LU 1 ,
  • Xu YANG 1 ,
  • Qinglin YU , 1,2
Expand
  • 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

Received date: 27 Nov 2008

Accepted date: 04 Dec 2008

Published date: 05 Jun 2009

Copyright

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg

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 defining 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.

Cite this article

Hongliang LU , Xu YANG , Qinglin YU . On vertex-coloring edge-weighting of graphs[J]. Frontiers of Mathematics in China, 2009 , 4(2) : 325 -334 . DOI: 10.1007/s11464-009-0014-8

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

2
Balister P N, Riordan O M, Schelp R H. Vertex-distinguishing edge colorings of graphs. J Graph Theory, 2003, 42: 95-109

DOI

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

5
Wang T, Yu Q. On vertex-coloring 13-edge-weighting. Front Math China, 2008, 3(4): 581-587

DOI

Options
Outlines

/