Homogeneous colourings of graphs

Tomáš Madaras; Mária Šurimová

Mathematica Bohemica (2023)

  • Volume: 148, Issue: 1, page 105-115
  • ISSN: 0862-7959

Abstract

top
A proper vertex k -colouring of a graph G is called l -homogeneous if the number of colours in the neigbourhood of each vertex of G equals l . We explore basic properties (the existence and the number of used colours) of homogeneous colourings of graphs in general as well as of some specific graph families, in particular planar graphs.

How to cite

top

Madaras, Tomáš, and Šurimová, Mária. "Homogeneous colourings of graphs." Mathematica Bohemica 148.1 (2023): 105-115. <http://eudml.org/doc/299466>.

@article{Madaras2023,
abstract = {A proper vertex $k$-colouring of a graph $G$ is called $l$-homogeneous if the number of colours in the neigbourhood of each vertex of $G$ equals $l$. We explore basic properties (the existence and the number of used colours) of homogeneous colourings of graphs in general as well as of some specific graph families, in particular planar graphs.},
author = {Madaras, Tomáš, Šurimová, Mária},
journal = {Mathematica Bohemica},
keywords = {proper colouring; homogeneous colouring; planar graph; triangulation},
language = {eng},
number = {1},
pages = {105-115},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Homogeneous colourings of graphs},
url = {http://eudml.org/doc/299466},
volume = {148},
year = {2023},
}

TY - JOUR
AU - Madaras, Tomáš
AU - Šurimová, Mária
TI - Homogeneous colourings of graphs
JO - Mathematica Bohemica
PY - 2023
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 148
IS - 1
SP - 105
EP - 115
AB - A proper vertex $k$-colouring of a graph $G$ is called $l$-homogeneous if the number of colours in the neigbourhood of each vertex of $G$ equals $l$. We explore basic properties (the existence and the number of used colours) of homogeneous colourings of graphs in general as well as of some specific graph families, in particular planar graphs.
LA - eng
KW - proper colouring; homogeneous colouring; planar graph; triangulation
UR - http://eudml.org/doc/299466
ER -

References

top
  1. Bala, K., Homogénne farbenia grafov: BSc. Thesis, P. J. Šafárik University in Košice, Košice (2016), Slovak. (2016) 
  2. Behzad, M., Chartrand, G., 10.2307/2315277, Am. Math. Mon. 74 (1967), 962-963. (1967) Zbl0179.52701MR0220627DOI10.2307/2315277
  3. Bujtás, C., Tuza, Z., 10.1016/j.disc.2008.04.019, Discrete Math. 309 (2009), 4890-4902. (2009) Zbl1210.05088MR2533435DOI10.1016/j.disc.2008.04.019
  4. Diks, K., Kowalik, L., Kurowski, M., 10.1007/3-540-36379-3_13, Graph-Theoretic Concepts in Computer Science Lecture Notes in Computer Science 2573. Springer, Berlin (2002), 138-149. (2002) Zbl1022.05500MR2063806DOI10.1007/3-540-36379-3_13
  5. Dobrynin, A. A., Gutman, I., Klavžar, S., Žigert, P., 10.1023/A:1016290123303, Acta Appl. Math. 72 (2002), 247-294. (2002) Zbl0993.05059MR1916949DOI10.1023/A:1016290123303
  6. Everett, M. G., Borgatti, S., 10.1016/0165-4896(91)90080-B, Math. Soc. Sci. 21 (1991), 183-188. (1991) Zbl0771.05037MR1113826DOI10.1016/0165-4896(91)90080-B
  7. Feder, T., Hell, P., Subi, C., 10.1016/j.ejc.2020.103210, Eur. J. Comb. 91 (2021), Article ID 103210, 15 pages. (2021) Zbl1458.05065MR4161804DOI10.1016/j.ejc.2020.103210
  8. Goddard, W., Wash, K., Xu, H., 10.7151/dmgt.1814, Discuss. Math. Graph Theory 35 (2015), 571-584. (2015) Zbl1317.05055MR3368990DOI10.7151/dmgt.1814
  9. Janicová, M., Madaras, T., Soták, R., Lužar, B., 10.26493/1855-3974.1083.54f, Ars Math. Contemp. 12 (2017), 351-360. (2017) Zbl1370.05065MR3646700DOI10.26493/1855-3974.1083.54f
  10. Jendrol', S., Maceková, M., 10.1016/j.disc.2014.09.014, Discrete Math. 338 (2015), 149-158. (2015) Zbl1302.05040MR3279266DOI10.1016/j.disc.2014.09.014
  11. Kramer, F., Kramer, H., 10.1016/j.disc.2006.11.059, Discrete Math. 308 (2008), 422-426. (2008) Zbl1130.05026MR2378044DOI10.1016/j.disc.2006.11.059
  12. Montgomery, B., Dynamic Coloring of Graphs: Ph.D. Thesis, West Virginia University, Morgantown (2001). (2001) MR2702379
  13. Roberts, F. S., Sheng, L., 10.1002/1097-0037(200103)37:2<67::AID-NET1>3.0.CO;2-9, Networks 37 (2001), 67-73. (2001) Zbl0991.91063MR1811997DOI10.1002/1097-0037(200103)37:2<67::AID-NET1>3.0.CO;2-9
  14. Tuza, Z., 10.26493/2590-9770.1234.37b, Art Discrete Appl. Math. 1 (2018), Article ID P2.05, 11 pages. (2018) Zbl1421.05068MR3997091DOI10.26493/2590-9770.1234.37b
  15. West, D. B., Introduction to Graph Theory, Prentice Hall, Upper Saddle River (1996). (1996) Zbl1121.05304MR1367739

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.