Independent systems of representatives in weighted graphs (Q2460628): Difference between revisions

It is conjectured that if the vertex set of a graph with maximal degree \(\Delta\) is partitioned into sets \(V_i\) of size \(2\Delta\), then there exists a colouring of the graph by \(2\Delta\) colours, where each colour class meets each \(V_i\) at precisely one vertex. The authors call it the strong \(2\Delta\)-colorability conjecture. They prove a fractional version of this conjecture. The considerations base on the theory of independent systems of representatives (an independent set of representatives is a choice of one vertex from each set \(V_i\) of a partition \(V_1,V_2,\dots,V_m\) of the vertex set of a graph if the selected points are pairwise non-adjacent) and a weighted generalization of a theorem of Haxell.