D-resolvability of vertices in planar graphs
James A. Tilley
Vol. 21, no. 4, pp. 649-661, 2017. Regular paper.
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.
Submitted: March 2017.
Accepted: April 2017.
Final: April 2017.
Published: June 2017.
Communicated by Giuseppe Liotta
article (PDF)