Abstract
In this paper we study the planar graphs that admit an acyclic 3-coloring. We show that testing acyclic 3-colorability is \(\cal NP\)-hard for planar graphs of maximum degree 4 and we show that there exist infinite classes of cubic planar graphs that are not acyclically 3-colorable. Further, we show that every planar graph has a subdivision with one vertex per edge that is acyclically 3-colorable. Finally, we characterize the series-parallel graphs such that every 3-coloring is acyclic and we provide a linear-time recognition algorithm for such graphs.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Albertson, M.O., Berman, D.: Every planar graph has an acyclic 7-coloring. Israel J. Math. 14, 390–408 (1973)
Alon, N., McDiarmid, C., Reed, B.A.: Acyclic coloring of graphs. Random Struct. Algorithms 2(3), 277–288 (1991)
Angelini, P., Frati, F.: Acyclically 3-colorable planar graphs. Tech. Report RT-DIA-147-2009, Dept. of Computer Science and Automation, University of Roma Tre. (2009), http://web.dia.uniroma3.it/ricerca/rapporti/rt/2009-147.pdf
Appel, K., Haken, W.: Every planar map is 4-colorable. Part I. Discharging. Illinois J. Math. 21(3), 429–490 (1977)
Appel, K., Haken, W., Koch, J.: Every planar map is 4-colorable. Part II. Reducibility. Illinois J. Math. 21(3), 491–567 (1977)
Borodin, O.V.: On acyclic colourings of planar graphs. Discr. Math. 25, 211–236 (1979)
Borodin, O.V., Kostochka, A.V., Woodall, D.R.: Acyclic colourings of planar graphs with large girth. J. London Math. Soc. 60(2), 344–352 (1999)
Brooks, R.L.: On coloring the nodes of a network. Proc. Cambridge Philos. Soc. 37, 194–197 (1941)
Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237–267 (1976)
Grünbaum, B.: Acyclic colorings of planar graphs. Israel J. Math. 14, 390–408 (1973)
Kostochka, A.V.: Acyclic 6-coloring of planar graphs. Metody Diskret. Anal. 28, 40–56 (1976)
Kostochka, A.V.: Upper Bounds of Chromatic Functions of Graphs. PhD thesis, University of Novosibirsk, in Russian (1978)
Kostochka, A.V., Melnikov, L.S.: To the paper of B. Grünbaum on acyclic colorings. Discrete Math. 14, 403–406 (1976)
Mitchem, J.: Every planar graph has an acyclic 8-coloring. Duke Math. J. 41, 177–181 (1974)
Robertson, N., Sanders, D.P., Seymour, P.D., Thomas, R.: Efficiently four-coloring planar graphs. In: STOC, pp. 571–575 (1996)
Skulrattanakulchai, S.: Acyclic colorings of subcubic graphs. Inf. Proc. Lett. 92(4), 161–167 (2004)
Valdes, J., Tarjan, R.E., Lawler, E.L.: The recognition of series parallel digraphs. SIAM J. Comput. 11(2), 298–313 (1982)
Wood, D.R.: Acyclic, star and oriented colourings of graph subdivisions. Discr. Math. Theor. Comp. Sc. 7(1), 37–50 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Angelini, P., Frati, F. (2010). Acyclically 3-Colorable Planar Graphs. In: Rahman, M.S., Fujita, S. (eds) WALCOM: Algorithms and Computation. WALCOM 2010. Lecture Notes in Computer Science, vol 5942. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11440-3_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-11440-3_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11439-7
Online ISBN: 978-3-642-11440-3
eBook Packages: Computer ScienceComputer Science (R0)