Note on partitions of planar graphs
Izak Broere ; Bonita S. Wilson ; Jozef Bucko
Discussiones Mathematicae Graph Theory, Tome 25 (2005), p. 211-215 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

Chartrand and Kronk in 1969 showed that there are planar graphs whose vertices cannot be partitioned into two parts inducing acyclic subgraphs. In this note we show that the same is true even in the case when one of the partition classes is required to be triangle-free only.

Publié le : 2005-01-01
EUDML-ID : urn:eudml:doc:270142 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1273,
     author = {Izak Broere and Bonita S. Wilson and Jozef Bucko},
     title = {Note on partitions of planar graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {25},
     year = {2005},
     pages = {211-215},
     zbl = {1075.05031},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1273}
}

Izak Broere; Bonita S. Wilson; Jozef Bucko. Note on partitions of planar graphs. Discussiones Mathematicae Graph Theory, Tome 25 (2005) pp. 211-215. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1273/

[000] [1] K. Appel and W. Haken, Every planar graph is four colourable, Illinois J. Math. 21 (1977) 429-567. | Zbl 0387.05010

[001] [2] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, A survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037. | Zbl 0902.05026

[002] [3] M. Borowiecki, I. Broere and P. Mihók, Minimal reducible bounds for planar graphs, Discrete Math. 212 (2000) 19-27, doi: 10.1016/S0012-365X(99)00205-8. | Zbl 0945.05022

[003] [4] G. Chartrand and H. H. Kronk, The point arboricity of planar graphs, J. London Math. Soc. 44 (1969) 612-616, doi: 10.1112/jlms/s1-44.1.612. | Zbl 0175.50505

[004] [5] T. Kaiser and R. Skrekovski, Planar graph colorings without short monochromatic cycles, J. Graph Theory 46 (2004) 25-38, doi: 10.1002/jgt.10167. | Zbl 1042.05044

[005] [6] K. Kuratowski, Sur le problème des courbes gauches en topologie, Fund. Math. 15 (1930) 271-283. | Zbl 56.1141.03

[006] [7] P. Mihók, Minimal reducible bound for outerplanar and planar graphs, Discrete Math. 150 (1996) 431-435, doi: 10.1016/0012-365X(95)00211-E. | Zbl 0911.05043

[007] [8] C. Thomassen, Decomposing a planar graph into degenerate graphs, J. Combin. Theory (B) 65 (1995) 305-314, doi: 10.1006/jctb.1995.1057. | Zbl 0840.05070