|
|
|
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 |
|
|
|
|
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 u ∈ V (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 uv ∈ E(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
|
|
| 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
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|