PDF(128 KB)
On vertex-coloring 13-edge-weighting
Author information
+
1.Center for Combinatorics, Key Laboratory of Pure Mathematics and Combinatorics, Ministry of Education of China, Nankai University; 2.Center for Combinatorics, Key Laboratory of Pure Mathematics and Combinatorics, Ministry of Education of China, Nankai University；Department of Mathematics and Statistics, Thompson Rivers University;
Show less
History
+
| Published |
| 05 Dec 2008 |
| Issue Date |
| 05 Dec 2008 |
L. Addario-Berry et al. [Discrete Appl. Math., 2008, 156: 1168–1174] have shown that there exists a 16-edge-weighting such that the induced vertex coloring is proper. In this note, we improve their result and prove that there exists a 13-edge-weighting of a graph G, such that its induced vertex coloring of G is proper. This result is one step close to the original conjecture posed by M. Karónski et al. [J. Combin. Theory, Ser. B, 2004, 91: 151–157].
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
This is a preview of subscription content, contact
us for subscripton.
References
1. Addario-Berry L, Dalal K, McDiarmid C, Reed B, Thomason A . Vertex-colouring edge-weightings. Combinatorica, 2007, 27: 1–12. doi:10.1007/s00493-007-0041-6
2. Addario-Berry L, Dalal K, Reed B . Degree constrained subgraphs. Discrete Appl Math, 2008, 156: 1168–1174. doi:10.1016/j.dam.2007.05.059
3. Karon´ski M, Luczak T, Thomason A . Edge weights and vertex colours. J Combin Theory, Ser B, 2004, 91: 151–157. doi:10.1016/j.jctb.2003.12.001
AI Summary
