Discussiones Mathematicae Graph Theory 26(3) (2006)
377-387
doi: 10.7151/dmgt.1330
Mieczysław Borowiecki and Anna Fiedorowicz
Faculty of Mathematics, Computer Science
and Econometrics, University of Zielona Góra
Prof. Z. Szafrana 4a, 65-516 Zielona Góra, Poland
e-mail: M.Borowiecki@wmie.uz.zgora.pl
e-mail: A.Fiedorowicz@wmie.uz.zgora.pl
Keywords: hereditary property, acyclic colouring, Ramsey class.
2000 Mathematics Subject Classification: 05C15, 05C75.
[1] | P. Boiron, E. Sopena and L. Vignal, Acyclic improper colorings of graphs, J. Graph Theory 32 (1999) 97-107, doi: 10.1002/(SICI)1097-0118(199909)32:1<97::AID-JGT9>3.0.CO;2-O. |
[2] | P. Boiron, E. Sopena and L. Vignal, Acyclic improper colourings of graphs with bounded degree, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 49 (1999) 1-9. |
[3] | O.V. Borodin, On acyclic colorings of planar graphs, Discrete Math. 25 (1979) 211-236, doi: 10.1016/0012-365X(79)90077-3. |
[4] | O.V. Borodin, A.V. Kostochka, A. Raspaud and E. Sopena, Acyclic colourings of 1-planar graphs, Discrete Applied Math. 114 (2001) 29-41, doi: 10.1016/S0166-218X(00)00359-0. |
[5] | O.V. Borodin, A.V. Kostochka and D.R. Woodall, Acyclic colorings of planar graphs with large girth, J. London Math. Soc. 60 (1999) 344-352, doi: 10.1112/S0024610799007942. |
[6] | M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, A survey of hereditary properties of graphs, Discussiones Mathematicae Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037. |
[7] | M.I. Burstein, Every 4-valent graph has an acyclic 5-coloring, Soobsc. Akad. Gruzin. SSR 93 (1979) 21-24 (in Russian). |
[8] | G. Ding, B. Oporowski, D.P. Sanders and D. Vertigan, Partitioning graphs of bounded tree-width, Combinatorica 18 (1998) 1-12, doi: 10.1007/s004930050001. |
[9] | R. Diestel, Graph Theory (Springer, Berlin, 1997). |
[10] | B. Grunbaum, Acyclic coloring of planar graphs, Israel J. Math. 14 (1973) 390-412, doi: 10.1007/BF02764716. |
[11] | P. Mihók and G. Semanišin, Reducible properties of graphs, Discuss. Math. Graph Theory 15 (1995) 11-18, doi: 10.7151/dmgt.1002. |
Received 11 January 2006
Revised 21 September 2006