On vertex-coloring edge-weighting of graphs |
| |
Authors: | Hongliang Lu Xu Yang Qinglin Yu |
| |
Institution: | 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-weighting w 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 c(u) = Σ
e∋u
w(e) 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 sufficient conditions for graphs to be vertex-coloring k-edge-weighting.
|
| |
Keywords: | Vertex coloring edge-weighting |
本文献已被 万方数据 SpringerLink 等数据库收录! |
| 点击此处可从《Frontiers of Mathematics in China》浏览原始摘要信息 |
| 点击此处可从《Frontiers of Mathematics in China》下载免费的PDF全文 |
|