Vertex-Colouring Edge-Weightings |
| |
| Authors: | Louigi Addario-Berry Ketan Dalal Colin McDiarmid Bruce A Reed Andrew Thomason |
| |
| Institution: | (1) School of Computer Science, McGill University University, St. Montreal, QC, H3A 2A7, Canada;(2) School of Computer Science, McGill University University, St. Montreal, QC, H3A 2A7, Canada;(3) Department of Statistics, University of Oxford, 1 South Parks Road, Oxford OX1 3TG, United Kingdom;(4) School of Computer Science, McGill University University, St. Montreal, QC, H3A 2A7, Canada;(5) DPMMS, Centre for Mathematical Sciences, Wilberforce Road, Cambridge CB3 0WB, United Kingdom |
| |
| Abstract: | A weighting w of the edges of a graph G induces a colouring of the vertices of G where the colour of vertex v, denoted cv, is
. We show that the edges of every graph that does not contain a component isomorphic to K2 can be weighted from the set {1, . . . ,30} such that in the resulting vertex-colouring of G, for every edge (u,v) of G, cu ≠cv. |
| |
| Keywords: | 05C15 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
