D-resolvability of vertices in planar graphs

Abstract

It is well known that a vertex of degree 5 in a planar graph is not $D$-reducible. However, it remains an open question whether all vertices in such a graph are $D$-resolvable. If so, it would be a stronger result than mere 4-colorability. To investigate the question, we designed and implemented two algorithms, one to 4-color a planar graph and the other to generate internally 6-connected triangulations randomly. The coloring algorithm greedily obtains a $k$-coloring and then, if $k > 4$ (highly likely), transforms the $k$-coloring into a 4-coloring solely by means of Kempe exchanges (generally possible only if all vertices are $D$-resolvable). We used the random generator to test the coloring algorithm systematically in over 200,000 trials that included many tens of thousands of non-isomorphic graphs. We also tested the algorithm on the graphs of Errera, Kittell, Heawood and others. We encountered no failures in any of the tests.