Note on partitions of planar graphs

• Autorzy: Izak Broere , Bonita S. Wilson , Jozef Bucko
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

planar graph; hereditary property of graphs; forest and triangle-free graph

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2005
• Tom: 25
• Numer: 1-2
• Strony: 211-215

Daty

wydano

2005

otrzymano

2003-12-05

poprawiono

2004-11-03

Twórcy

autor

Izak Broere

• Rand Afrikaans University, Johannesburg, Republic of South Africa

autor

Bonita S. Wilson

• Rand Afrikaans University, Johannesburg, Republic of South Africa

autor

Jozef Bucko

• Department of Applied Mathematics, Faculty of Economics, Technical University, B. Nĕmcovej, 040 01 Košice, Slovak Republic

Bibliografia

• [1] K. Appel and W. Haken, Every planar graph is four colourable, Illinois J. Math. 21 (1977) 429-567.
• [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.
• [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.
• [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.
• [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.
• [6] K. Kuratowski, Sur le problème des courbes gauches en topologie, Fund. Math. 15 (1930) 271-283.
• [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.
• [8] C. Thomassen, Decomposing a planar graph into degenerate graphs, J. Combin. Theory (B) 65 (1995) 305-314, doi: 10.1006/jctb.1995.1057.

Identyfikatory

DOI

10.7151/dmgt.1273