On a 1,2 Conjecture
Jakub Przybyło, Mariusz Woźniak
Abstract
Let us assign positive integers to the edges and vertices of a
simple graph G. As a result we obtain a
vertex-colouring of G with integers, where a vertex
colour is simply a sum of the weight assigned to the vertex itself
and the weights of its incident edges. Can we obtain a proper
colouring using only weights 1 and 2 for an arbitrary
G?
We give a positive answer when G is a 3-colourable, complete or 4-regular graph. We also show that it is enough to use weights from 1 to 11, as well as from 1 to ⌊χ(G) / 2⌋+1, for an arbitrary graph G.
We give a positive answer when G is a 3-colourable, complete or 4-regular graph. We also show that it is enough to use weights from 1 to 11, as well as from 1 to ⌊χ(G) / 2⌋+1, for an arbitrary graph G.
Full Text: PDF PostScript