Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
proper colouring; homogeneous colouring; planar graph; triangulation
proper colouring; homogeneous colouring; planar graph; triangulation
Summary:
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.
References:
[1] Bala, K.: Homogénne farbenia grafov: BSc. Thesis. P. J. Šafárik University in Košice, Košice (2016), Slovak.
[2] Behzad, M., Chartrand, G.: No graph is perfect. Am. Math. Mon. 74 (1967), 962-963. DOI 10.2307/2315277 | MR 0220627 | Zbl 0179.52701
[3] Bujtás, C., Tuza, Z.: Color-bounded hypergraphs. I. General results. Discrete Math. 309 (2009), 4890-4902. DOI 10.1016/j.disc.2008.04.019 | MR 2533435 | Zbl 1210.05088
[4] Diks, K., Kowalik, L., Kurowski, M.: A new 3-color criterion for planar graphs. Graph-Theoretic Concepts in Computer Science Lecture Notes in Computer Science 2573. Springer, Berlin (2002), 138-149. DOI 10.1007/3-540-36379-3_13 | MR 2063806 | Zbl 1022.05500
[5] Dobrynin, A. A., Gutman, I., Klavžar, S., Žigert, P.: Wiener index of hexagonal systems. Acta Appl. Math. 72 (2002), 247-294. DOI 10.1023/A:1016290123303 | MR 1916949 | Zbl 0993.05059
[6] Everett, M. G., Borgatti, S.: Role colouring a graph. Math. Soc. Sci. 21 (1991), 183-188. DOI 10.1016/0165-4896(91)90080-B | MR 1113826 | Zbl 0771.05037
[7] Feder, T., Hell, P., Subi, C.: Distance-two colourings of Barnette graphs. Eur. J. Comb. 91 (2021), Article ID 103210, 15 pages. DOI 10.1016/j.ejc.2020.103210 | MR 4161804 | Zbl 1458.05065
[8] Goddard, W., Wash, K., Xu, H.: WORM colorings. Discuss. Math. Graph Theory 35 (2015), 571-584. DOI 10.7151/dmgt.1814 | MR 3368990 | Zbl 1317.05055
[9] Janicová, M., Madaras, T., Soták, R., Lužar, B.: From NMNR-coloring of hypergraphs to homogenous coloring of graphs. Ars Math. Contemp. 12 (2017), 351-360. DOI 10.26493/1855-3974.1083.54f | MR 3646700 | Zbl 1370.05065
[10] Jendrol', S., Maceková, M.: Describing short paths in plane graphs of girth at least 5. Discrete Math. 338 (2015), 149-158. DOI 10.1016/j.disc.2014.09.014 | MR 3279266 | Zbl 1302.05040
[11] Kramer, F., Kramer, H.: A survey on the distance-colouring of graphs. Discrete Math. 308 (2008), 422-426. DOI 10.1016/j.disc.2006.11.059 | MR 2378044 | Zbl 1130.05026
[12] Montgomery, B.: Dynamic Coloring of Graphs: Ph.D. Thesis. West Virginia University, Morgantown (2001). MR 2702379
[13] Roberts, F. S., Sheng, L.: How hard is it to determine if a graph has a 2-role assignment?. Networks 37 (2001), 67-73. DOI 10.1002/1097-0037(200103)37:2<67::AID-NET1>3.0.CO;2-9 | MR 1811997 | Zbl 0991.91063
[14] Tuza, Z.: Mixed hypergraphs and beyond. Art Discrete Appl. Math. 1 (2018), Article ID P2.05, 11 pages. DOI 10.26493/2590-9770.1234.37b | MR 3997091 | Zbl 1421.05068
[15] West, D. B.: Introduction to Graph Theory. Prentice Hall, Upper Saddle River (1996). MR 1367739 | Zbl 1121.05304
Search
Partner of
