|
|
|
On vertex-coloring 13-edge-weighting |
| WANG Tao1, YU Qinglin2 |
| 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; |
|
|
|
|
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].
|
|
Issue Date: 05 December 2008
|
|
| 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
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
