View Related Documents

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 $ {\sum\nolimits_{e \mathrel\backepsilon v} {w{\left( e \right)}} } $ {\sum\nolimits_{e \mathrel\backepsilon v} {w{\left( e \right)}} } . 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, cucv.

Mathematics Subject Classification (2000):  05C15

Fulltext Preview

Image of the first page of the fulltext document