Graph multicoloring reduction methods and application to McDiarmid-Reed's Conjecture
share
A (a,b)-coloring of a graph G associates to each vertex a set of b colors from a set of a colors in such a way that the color-sets of adjacent vertices are disjoints. We define general reduction tools for (a,b)-coloring of graphs for 2< a/b< 3. In particular, we prove necessary and sufficient conditions for the existence of a (a,b)-coloring of a path with prescribed color-sets on its end-vertices. Other more complex (a,b)-colorability reductions are presented. The utility of these tools is exemplified on finite triangle-free induced subgraphs of the triangular lattice. Computations on millions of such graphs generated randomly show that our tools allow to find (in linear time) a (9,4)-coloring for each of them. Although there remain few graphs for which our tools are not sufficient for finding a (9,4)-coloring, we believe that pursuing our method can lead to a solution of the conjecture of McDiarmid-Reed.
READ FULL TEXT