Frontiers of Mathematics in China >

2008 , Vol. 3 >Issue 4: 581 - 587

DOI: https://doi.org/10.1007/s11464-008-0041-x

On vertex-coloring 13-edge-weighting

Expand
  • 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;

Published date: 05 Dec 2008

Fold

Abstract

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

Cite this article

WANG Tao, YU Qinglin . On vertex-coloring 13-edge-weighting[J]. Frontiers of Mathematics in China, 2008 , 3(4) : 581 -587 . DOI: 10.1007/s11464-008-0041-x

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
Options
Outlines

/

〈 〉