| Title:
|
Homogeneous colourings of graphs (English) |
| Author:
|
Madaras, Tomáš |
| Author:
|
Šurimová, Mária |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
148 |
| Issue:
|
1 |
| Year:
|
2023 |
| Pages:
|
105-115 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
proper colouring |
| Keyword:
|
homogeneous colouring |
| Keyword:
|
planar graph |
| Keyword:
|
triangulation |
| MSC:
|
05C15 |
| idZBL:
|
Zbl 07655816 |
| idMR:
|
MR4536313 |
| DOI:
|
10.21136/MB.2022.0007-21 |
| . |
| Date available:
|
2023-02-03T11:23:36Z |
| Last updated:
|
2023-09-13 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/151530 |
| . |
| Reference:
|
[1] Bala, K.: Homogénne farbenia grafov: BSc. Thesis.P. J. Šafárik University in Košice, Košice (2016), Slovak. |
| Reference:
|
[2] Behzad, M., Chartrand, G.: No graph is perfect.Am. Math. Mon. 74 (1967), 962-963. Zbl 0179.52701, MR 0220627, 10.2307/2315277 |
| Reference:
|
[3] Bujtás, C., Tuza, Z.: Color-bounded hypergraphs. I. General results.Discrete Math. 309 (2009), 4890-4902. Zbl 1210.05088, MR 2533435, 10.1016/j.disc.2008.04.019 |
| Reference:
|
[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. Zbl 1022.05500, MR 2063806, 10.1007/3-540-36379-3_13 |
| Reference:
|
[5] Dobrynin, A. A., Gutman, I., Klavžar, S., Žigert, P.: Wiener index of hexagonal systems.Acta Appl. Math. 72 (2002), 247-294. Zbl 0993.05059, MR 1916949, 10.1023/A:1016290123303 |
| Reference:
|
[6] Everett, M. G., Borgatti, S.: Role colouring a graph.Math. Soc. Sci. 21 (1991), 183-188. Zbl 0771.05037, MR 1113826, 10.1016/0165-4896(91)90080-B |
| Reference:
|
[7] Feder, T., Hell, P., Subi, C.: Distance-two colourings of Barnette graphs.Eur. J. Comb. 91 (2021), Article ID 103210, 15 pages. Zbl 1458.05065, MR 4161804, 10.1016/j.ejc.2020.103210 |
| Reference:
|
[8] Goddard, W., Wash, K., Xu, H.: WORM colorings.Discuss. Math. Graph Theory 35 (2015), 571-584. Zbl 1317.05055, MR 3368990, 10.7151/dmgt.1814 |
| Reference:
|
[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. Zbl 1370.05065, MR 3646700, 10.26493/1855-3974.1083.54f |
| Reference:
|
[10] Jendrol', S., Maceková, M.: Describing short paths in plane graphs of girth at least 5.Discrete Math. 338 (2015), 149-158. Zbl 1302.05040, MR 3279266, 10.1016/j.disc.2014.09.014 |
| Reference:
|
[11] Kramer, F., Kramer, H.: A survey on the distance-colouring of graphs.Discrete Math. 308 (2008), 422-426. Zbl 1130.05026, MR 2378044, 10.1016/j.disc.2006.11.059 |
| Reference:
|
[12] Montgomery, B.: Dynamic Coloring of Graphs: Ph.D. Thesis.West Virginia University, Morgantown (2001). MR 2702379 |
| Reference:
|
[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. Zbl 0991.91063, MR 1811997, 10.1002/1097-0037(200103)37:2<67::AID-NET1>3.0.CO;2-9 |
| Reference:
|
[14] Tuza, Z.: Mixed hypergraphs and beyond.Art Discrete Appl. Math. 1 (2018), Article ID P2.05, 11 pages. Zbl 1421.05068, MR 3997091, 10.26493/2590-9770.1234.37b |
| Reference:
|
[15] West, D. B.: Introduction to Graph Theory.Prentice Hall, Upper Saddle River (1996). Zbl 1121.05304, MR 1367739 |
| . |
