Geodesic
Homogeneous colourings of graphs
Mathematica Bohemica, Tome 148 (2023) no. 1, pp. 105-115
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/MB.2022.0007-21
Classification : 05C15
Keywords: proper colouring; homogeneous colouring; planar graph; triangulation 
@article{10_21136_MB_2022_0007_21,
     author = {Madaras, Tom\'a\v{s} and \v{S}urimov\'a, M\'aria},
     title = {Homogeneous colourings of graphs},
     journal = {Mathematica Bohemica},
     pages = {105--115},
     year = {2023},
     volume = {148},
     number = {1},
     doi = {10.21136/MB.2022.0007-21},
     mrnumber = {4536313},
     zbl = {07655816},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2022.0007-21/}
}
TY  - JOUR
AU  - Madaras, Tomáš
AU  - Šurimová, Mária
TI  - Homogeneous colourings of graphs
JO  - Mathematica Bohemica
PY  - 2023
SP  - 105
EP  - 115
VL  - 148
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2022.0007-21/
DO  - 10.21136/MB.2022.0007-21
LA  - en
ID  - 10_21136_MB_2022_0007_21
ER  - 
%0 Journal Article
%A Madaras, Tomáš
%A Šurimová, Mária
%T Homogeneous colourings of graphs
%J Mathematica Bohemica
%D 2023
%P 105-115
%V 148
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2022.0007-21/
%R 10.21136/MB.2022.0007-21
%G en
%F 10_21136_MB_2022_0007_21
Madaras, Tomáš; Šurimová, Mária. Homogeneous colourings of graphs. Mathematica Bohemica, Tome 148 (2023) no. 1, pp. 105-115. doi: 10.21136/MB.2022.0007-21

[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 | MR | JFM

[3] Bujtás, C., Tuza, Z.: Color-bounded hypergraphs. I. General results. Discrete Math. 309 (2009), 4890-4902. | DOI | MR | JFM

[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 | MR | JFM

[5] Dobrynin, A. A., Gutman, I., Klavžar, S., Žigert, P.: Wiener index of hexagonal systems. Acta Appl. Math. 72 (2002), 247-294. | DOI | MR | JFM

[6] Everett, M. G., Borgatti, S.: Role colouring a graph. Math. Soc. Sci. 21 (1991), 183-188. | DOI | MR | JFM

[7] Feder, T., Hell, P., Subi, C.: Distance-two colourings of Barnette graphs. Eur. J. Comb. 91 (2021), Article ID 103210, 15 pages. | DOI | MR | JFM

[8] Goddard, W., Wash, K., Xu, H.: WORM colorings. Discuss. Math. Graph Theory 35 (2015), 571-584. | DOI | MR | JFM

[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 | MR | JFM

[10] Jendrol', S., Maceková, M.: Describing short paths in plane graphs of girth at least 5. Discrete Math. 338 (2015), 149-158. | DOI | MR | JFM

[11] Kramer, F., Kramer, H.: A survey on the distance-colouring of graphs. Discrete Math. 308 (2008), 422-426. | DOI | MR | JFM

[12] Montgomery, B.: Dynamic Coloring of Graphs: Ph.D. Thesis. West Virginia University, Morgantown (2001). | MR

[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 | MR | JFM

[14] Tuza, Z.: Mixed hypergraphs and beyond. Art Discrete Appl. Math. 1 (2018), Article ID P2.05, 11 pages. | DOI | MR | JFM

[15] West, D. B.: Introduction to Graph Theory. Prentice Hall, Upper Saddle River (1996). | MR | JFM

Cité par Sources :