Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00433
Dresolvability of vertices in planar graphs
James A. Tilley
Vol. 21, no. 4, pp. 649661, 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 4colorability. To investigate the question, we designed and implemented two algorithms, one to 4color a planar graph and the other to generate internally 6connected triangulations randomly. The coloring algorithm greedily obtains a $k$coloring and then, if $k > 4$ (highly likely), transforms the $k$coloring into a 4coloring 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 nonisomorphic 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
