Construction of acyclically 4-colourable planar triangulations with minimum degree 4

References

• M.O. Albertson and D.M. Berman, Every planar graph has an acyclic 7-coloring, Isr. J. Math. 28 (1977), pp. 169–174. doi: 10.1007/BF02759792
   Web of Science ®Google Scholar
• D. Barnette, On generating planar graphs, Discrete. Math. 7 (1974), pp. 199–208. doi: 10.1016/0012-365X(74)90035-1
   Google Scholar
• V. Batagelj, An inductive definition of the class of all triangulations with no vertex of degree smaller than 5. Proceedings of the Fourth Yugoslav Seminar on Graph Theory, Novi Sad. 1983, pp. 15–25.
   Google Scholar
• V. Batagelj, An improved inductive definition of two restricted classes of triangulations of the plane. in Combinatorics and Graph Theory, Banach Center Publications, 25, PWN - Polish Scientific Publishers, Warsaw, 1989, pp. 11–18.
   Google Scholar
• J.A. Bondy and U.S.R. Murty, Graph theory, Springer, New York, 2008.
   Google Scholar
• O.V. Borodin, A proof of Grünbaum's conjecture on the acyclic 5-colorability of planar graphs, Dokl. Akad. Nauk SSSR 231 (1976), pp. 18–20.
   Google Scholar
• O.V. Borodin, Acyclic 4-coloring of planar graphs without 4- and 5-cycles, J. Appl. Ind. Math. 5 (2011), pp. 31–43. doi: 10.1134/S1990478911010042
   Google Scholar
• O.V. Borodin, Acyclic 4-choosability of planar graphs with no 4- and 5-cycles, J. Graph Theory 72 (2013), pp. 374–397. doi: 10.1002/jgt.21647
   Web of Science ®Google Scholar
• P. Bose and F. Hurtado, Flips in planar graphs, Comput. Geom. 42 (2009), pp. 60–80. doi: 10.1016/j.comgeo.2008.04.001
   Web of Science ®Google Scholar
• P. Bose and S. Verdonschot, A history of flips in combinatorial triangulations. in Computational Geometry, Lecture Notes in Computer Science. Vol. 7579, Springer, Berlin, 2012, pp. 29–44.
   Google Scholar
• R. Bowen and S. Fisk, Generation of triangulations of the sphere, Math. Comput. 21 (1967), pp. 250–252.
   Web of Science ®Google Scholar
• G. Brinkmann and B.D. McKay, Construction of planar triangulations with minimum degree 5, Discrete. Math. 301 (2005), pp. 147–163. doi: 10.1016/j.disc.2005.06.019
   Web of Science ®Google Scholar
• G. Brinkmann and B.D. McKay, Fast generation of planar graphs, MATCH Commun. Math. Comput. Chem 58(2) (2007), pp. 323–357.
   Web of Science ®Google Scholar
• J.W. Bulter, A generation procedure for the simple 3-polytopes with cyclically 5-connected graphs, Can. J. Math 3 (1974), pp. 686–708.
   Google Scholar
• M. Chen and A. Raspaud, A sufficient condition for planar graphs to be acyclically 5-choosable, J. Graph Theory 70(2) (2012), pp. 135–151. doi: 10.1002/jgt.20604
   Web of Science ®Google Scholar
• M. Chen and A. Raspaud, Planar graphs without 4- and 5-cycles are acyclically 4-choosable, Discrete Appl. Math. 161(7) (2013), pp. 921–931. doi: 10.1016/j.dam.2012.11.006
   Web of Science ®Google Scholar
• V. Eberhard, Zur Morphologie der Polyeder, Teubner, Leipzig, 1891.
   Google Scholar
• B. Gr”unbaum, Acyclic colorings of planar graphs, Isr. J. Math. 14 (1973), pp. 390–408. doi: 10.1007/BF02764716
   Web of Science ®Google Scholar
• J. Hou and G. Liu, Every toroidal graph is acyclically 8-choosable, Acta. Math. Sin. Engl. Ser. 30(2) (2014), pp. 343–352. doi: 10.1007/s10114-013-1497-5
   Web of Science ®Google Scholar
• J. Hou and S. Wu, Acyclic coloring of graphs without bichromatic long path, Front. Math. China. 10(6) (2015), pp. 1343–1354. doi: 10.1007/s11464-015-0497-4
   Web of Science ®Google Scholar
• A.V. Kostochka, Acyclic 6-coloring of planar graphs, Discretny analys 28 (1976), pp. 40–56.
   Google Scholar
• A.V. Kostochka and L. Mel'nikov, Note to the paper of Gr”unbaum on acyclic colorings, Discrete. Math. 14 (1976), pp. 403–406. doi: 10.1016/0012-365X(76)90075-3
   Web of Science ®Google Scholar
• J. Mitchem, Every planar graph has an acyclic 8-coloring, Duke Math. J. 41 (1974), pp. 177–181. doi: 10.1215/S0012-7094-74-04119-2
   Web of Science ®Google Scholar
• O. Ore, The four-color problem, Academic Press, New York, 1967.
   Google Scholar
• K. Wagner, Bemerkungen zum vierfarbenproblem, Jahresbericht der Deutschen Mathematiker-Vereinigung 46 (1936), pp. 26–32.
   Google Scholar