Note on partitions of planar graphs

Izak Broere; Bonita S. Wilson; Jozef Bucko

Discussiones Mathematicae Graph Theory (2005)

  • Volume: 25, Issue: 1-2, page 211-215
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Izak Broere, Bonita S. Wilson, and Jozef Bucko. "Note on partitions of planar graphs." Discussiones Mathematicae Graph Theory 25.1-2 (2005): 211-215. <http://eudml.org/doc/270142>.

@article{IzakBroere2005,
abstract = {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.},
author = {Izak Broere, Bonita S. Wilson, Jozef Bucko},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {planar graph; hereditary property of graphs; forest and triangle-free graph; triangle-free graph},
language = {eng},
number = {1-2},
pages = {211-215},
title = {Note on partitions of planar graphs},
url = {http://eudml.org/doc/270142},
volume = {25},
year = {2005},
}

TY - JOUR
AU - Izak Broere
AU - Bonita S. Wilson
AU - Jozef Bucko
TI - Note on partitions of planar graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2005
VL - 25
IS - 1-2
SP - 211
EP - 215
AB - 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.
LA - eng
KW - planar graph; hereditary property of graphs; forest and triangle-free graph; triangle-free graph
UR - http://eudml.org/doc/270142
ER -

References

top
  1. [1] K. Appel and W. Haken, Every planar graph is four colourable, Illinois J. Math. 21 (1977) 429-567. Zbl0387.05010
  2. [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. Zbl0902.05026
  3. [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. Zbl0945.05022
  4. [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. Zbl0175.50505
  5. [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. Zbl1042.05044
  6. [6] K. Kuratowski, Sur le problème des courbes gauches en topologie, Fund. Math. 15 (1930) 271-283. Zbl56.1141.03
  7. [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. Zbl0911.05043
  8. [8] C. Thomassen, Decomposing a planar graph into degenerate graphs, J. Combin. Theory (B) 65 (1995) 305-314, doi: 10.1006/jctb.1995.1057. Zbl0840.05070

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.