Hamiltonicity and Generalised Total Colourings of Planar Graphs

Mieczysław Borowiecki; Izak Broere

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 2, page 243-257
  • ISSN: 2083-5892

Abstract

top
The total generalised colourings considered in this paper are colourings of graphs such that the vertices and edges of the graph which receive the same colour induce subgraphs from two prescribed hereditary graph properties while incident elements receive different colours. The associated total chromatic number is the least number of colours with which this is possible. We study such colourings for sets of planar graphs and determine, in particular, upper bounds for these chromatic numbers for proper colourings of the vertices while the monochromatic edge sets are allowed to be forests. We also prove that if an even planar triangulation has a Hamilton cycle H for which there is no cycle among the edges inside H, then such a graph needs at most four colours for a total colouring as described above. The paper is concluded with some conjectures and open problems.

How to cite

top

Mieczysław Borowiecki, and Izak Broere. "Hamiltonicity and Generalised Total Colourings of Planar Graphs." Discussiones Mathematicae Graph Theory 36.2 (2016): 243-257. <http://eudml.org/doc/277131>.

@article{MieczysławBorowiecki2016,
abstract = {The total generalised colourings considered in this paper are colourings of graphs such that the vertices and edges of the graph which receive the same colour induce subgraphs from two prescribed hereditary graph properties while incident elements receive different colours. The associated total chromatic number is the least number of colours with which this is possible. We study such colourings for sets of planar graphs and determine, in particular, upper bounds for these chromatic numbers for proper colourings of the vertices while the monochromatic edge sets are allowed to be forests. We also prove that if an even planar triangulation has a Hamilton cycle H for which there is no cycle among the edges inside H, then such a graph needs at most four colours for a total colouring as described above. The paper is concluded with some conjectures and open problems.},
author = {Mieczysław Borowiecki, Izak Broere},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {even planar triangulation; total colouring; Hamilton cycle; hereditary property},
language = {eng},
number = {2},
pages = {243-257},
title = {Hamiltonicity and Generalised Total Colourings of Planar Graphs},
url = {http://eudml.org/doc/277131},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Mieczysław Borowiecki
AU - Izak Broere
TI - Hamiltonicity and Generalised Total Colourings of Planar Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 2
SP - 243
EP - 257
AB - The total generalised colourings considered in this paper are colourings of graphs such that the vertices and edges of the graph which receive the same colour induce subgraphs from two prescribed hereditary graph properties while incident elements receive different colours. The associated total chromatic number is the least number of colours with which this is possible. We study such colourings for sets of planar graphs and determine, in particular, upper bounds for these chromatic numbers for proper colourings of the vertices while the monochromatic edge sets are allowed to be forests. We also prove that if an even planar triangulation has a Hamilton cycle H for which there is no cycle among the edges inside H, then such a graph needs at most four colours for a total colouring as described above. The paper is concluded with some conjectures and open problems.
LA - eng
KW - even planar triangulation; total colouring; Hamilton cycle; hereditary property
UR - http://eudml.org/doc/277131
ER -

References

top
  1. [1] O.V. Borodin, On acyclic colorings of planar graphs, Discrete Math. 25 (1979) 211-236. doi:10.1016/0012-365X(79)90077-3[Crossref] 
  2. [2] O.V. Borodin, A.V. Kostochka and D.R. Woodall, Acyclic colourings of planar graphs with large girth, J. Lond. Math. Soc. 60 (1999) 344-352. doi:10.1112/S0024610799007942[Crossref] Zbl0940.05032
  3. [3] 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[Crossref] Zbl0902.05026
  4. [4] M. Borowiecki, A. Kemnitz, M. Marangio and P. Mihók, Generalized total colorings of graphs, Discuss. Math. Graph Theory 31 (2011) 209-222. doi:10.7151/dmgt.1540[Crossref][WoS] Zbl1234.05076
  5. [5] G. Chartrand, H.V. Kronk and C.E. Wall, The point-arboricity of a graph, Israel J. Math. 6 (1968) 169-175. doi:10.1007/BF02760181[Crossref] Zbl0164.54201
  6. [6] R. Diestel, Graph Theory (Springer-Verlag, Berlin, 1997). 
  7. [7] G. Ding, B. Oporowski, D.P. Sanders and D. Vertigan, Surfaces, tree-width, cliqueminors, and partitions, J. Combin. Theory Ser. B 79 (2000) 221-246. Zbl1029.05041
  8. [8] R.B. Eggleton, Rectilinear drawings of graphs, Util. Math. 29 (1986) 149-172. doi:10.1006/jetb.2000.1962[Crossref] Zbl0578.05016
  9. [9] A.V. Kostochka and L.S. Mel′nikov, Note to the paper of Gr¨unbaum on acyclic colorings, Discrete Math. 14 (1976) 403-406. doi:10.1016/0012-365X(76)90075-3[Crossref] 
  10. [10] M. Król, On a sufficient and necessary condition of 3-colorableness for the planar graphs I, Pr. Nauk. Inst. Mat. Fiz. Teoret. PWr. 6 (1972) 37-40. 
  11. [11] G. Ringel, Ein sechsfarbenproblem auf der Kugel, Abh. Math. Semin. Univ. Hambg. 29 (1965) 107-117. doi:10.1007/BF02996313[Crossref] Zbl0132.20701
  12. [12] G. Ringel, Two trees in maximal planar bipartite graphs, J. Graph Theory 17 (1993) 755-758. doi:10.1002/jgt.3190170610[Crossref] 
  13. [13] X. Zhang, G. Liu and J.-L. Wu, Edge covering pseudo-outerplanar graphs with forests, Discrete Math. 312 (2012) 2788-2799. doi:10.1016/j.disc.2012.05.017[WoS][Crossref] Zbl1248.05053

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.