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) BibTeX