On a 1, 2 Conjecture
Jakub Przybylo, Mariusz WoźniaK
Source abstract
Graphs and Algorithms 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 C use weights from 1 to 11, as well as from 1 to 11 [chi(G)/2] + 1, for an arbitrary graph G.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.