Geodesic
On perfect colorings of infinite multipath graphs
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 2084-2095.

Voir la notice de l'article provenant de la source Math-Net.Ru

A coloring of vertices of a given graph is called perfect if the color structure of each sphere of radius $1$ in the graph depends only on the color of the sphere center. Let $n$ be a positive integer. We consider a lexicographic product of the infinite path graph and a graph $G$ that can be either the complete or empty graph on $n$ vertices. We give a complete description of perfect colorings with an arbitrary number of colors of such graph products.
Keywords: perfect coloring, equivalent colors, infinite multipath graph.
Mots-clés : equitable partition 
@article{SEMR_2020_17_a77,
     author = {M. A. Lisitsyna and S. V. Avgustinovich and O. G. Parshina},
     title = {On perfect colorings of infinite multipath graphs},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {2084--2095},
     publisher = {mathdoc},
     volume = {17},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2020_17_a77/}
}
TY  - JOUR
AU  - M. A. Lisitsyna
AU  - S. V. Avgustinovich
AU  - O. G. Parshina
TI  - On perfect colorings of infinite multipath graphs
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2020
SP  - 2084
EP  - 2095
VL  - 17
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2020_17_a77/
LA  - en
ID  - SEMR_2020_17_a77
ER  - 
%0 Journal Article
%A M. A. Lisitsyna
%A S. V. Avgustinovich
%A O. G. Parshina
%T On perfect colorings of infinite multipath graphs
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2020
%P 2084-2095
%V 17
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2020_17_a77/
%G en
%F SEMR_2020_17_a77
M. A. Lisitsyna; S. V. Avgustinovich; O. G. Parshina. On perfect colorings of infinite multipath graphs. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 2084-2095. http://geodesic.mathdoc.fr/item/SEMR_2020_17_a77/

[1] S.V. Avgustinovich, D.S. Krotov, A. Yu. Vasil'eva, “Completely regular codes in the infinite hexagonal grid”, Sib. Electron. Math. Izv., 13 (2016), 987–1016 | MR | Zbl

[2] S.V. Avgustinovich, A. Yu. Vasil'eva, I.V. Sergeeva, “Distance-regular colorings of the infinite rectangular grid”, Diskretn. Anal. Issled. Oper., 18:3 (2011), 3–10 | MR | Zbl

[3] M. Axenovich, “On multiple coverings of the infinite rectangular grid with balls of constant radius”, Discrete Math., 268:1–3 (2003), 31–48 | DOI | MR | Zbl

[4] P. Camion, B. Courteau, G. Fournier, S.V. Kanetkar, “Weight distribution of translates of linear codes and generalized Pless indentities”, J. Inf. Optim. Sci., 8 (1987), 1–23 | MR | Zbl

[5] P. Delsarte, “An algebraic approach to the association schemes of coding theory”, Philips Research Reports, 10, Historical Jrl., Ann Arbor, MI, 1973 | MR | Zbl

[6] C. Godsil, “Compact graphs and equitable partitions”, Linear Algebra Appl., 255 (1997), 259–266 | DOI | MR | Zbl

[7] F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1994 ; 1969 | MR | Zbl

[8] D.B. Khoroshilova, “On the parameters of perfect 2-colorings of circulant graphs”, Diskretn. Anal. Issled. Oper., 18:6 (2011), 82–89 | MR | Zbl

[9] D.B. Khoroshilova, “On circular perfect two-color colorings”, Diskretn. Anal. Issled. Oper., 16:1 (2009), 80–92 | MR | Zbl

[10] D. Krizanc, M. Lafond, L. Narayanan, J. Opatrny, S. Shende, “Satisfying neighbor preferences on a circle”, LATIN 2018, Lecture Notes in Computer Science, 10807, eds. M. Bender et al., Springer, Cham, 2018, 727–740 | DOI | MR | Zbl

[11] D.S. Krotov, Perfect colorings of $Z^2$: Nine colors, 2009, arXiv: 0901.0004

[12] M.A. Lisitsyna, S.V. Avgustinovich, “Perfect colorings of prism graph”, Sib. Electron. Mat. Izv., 13 (2016), 1116–1128 | MR | Zbl

[13] M.A. Lisitsyna, O.G. Parshina, “Perfect colorings of the infinite circulant graph with distances 1 and 2”, J. Appl. Ind. Math., 11:3 (2017), 381–388 | DOI | MR | Zbl

[14] O.G. Parshina, “Perfect 2-colorings of infinite circulant graphs with a continuous set of distances”, J. Appl. Ind. Math., 8:3 (2014), 357–361 | DOI | MR | Zbl

[15] O.G. Parshina, M.A. Lisitsyna, “The perfect 2-colorings of infinite circulant graphs with a continuous set of odd distances”, Sib. Electron. Mat. Izv., 17 (2020), 590–603 | DOI | MR | Zbl

[16] S.A. Puzynina, “On periodicity of perfect colorings of the infinite hexagonal and triangular grids”, Sib. Math. J., 52:1 (2011), 91–104 | DOI | MR | Zbl

[17] S.A. Puzynina, “Perfect colorings of vertices of the graph $G_{Z^{2}}$ in three colors”, Diskretn. Anal. Issled. Oper., Ser. 2, 12:1 (2005), 37–54 | MR | Zbl

[18] S.A. Puzynina, “Periodicity of perfect colorings of an infinite rectangular grid”, Diskretn. Anal. Issled. Oper., Ser. 1, 11:1 (2004), 79–92 | MR | Zbl

[19] S.A. Puzynina, S.V. Avgustinovich, “On periodicity of two-dimensional words”, Theor. Comput. Sci., 391:1–2 (2008), 178–187 | DOI | MR | Zbl

[20] A. Yu. Vasil'eva, “Distance regular colorings of the infinite triangular grid”, Collection of Abstracts of the International Conference “Mal'tsev Meeting”, 2014, 98