Geodesic
The perfect $2$-colorings of infinite circulant graphs with a continuous set of odd distances
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 590-603.

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

A vertex coloring of a given simple graph $G=(V,E)$ with $k$ colors ($k$-coloring) is a map from its vertex set to the set of integers $\{1,2,3,\dots, k\}$. A coloring is called perfect if the multiset of colors appearing on the neighbours of any vertex depends only on the color of the vertex. We consider perfect colorings of Cayley graphs of the additive group of integers with generating set $\{1,-1,3,-3,5,-5,\dots, 2n-1,1-2n\}$ for a positive integer $n$. We enumerate perfect $2$-colorings of the graphs under consideration and state the conjecture generalizing the main result to an arbitrary number of colors.
Keywords: perfect coloring, Cayley graph
Mots-clés : circulant graph, equitable partition. 
@article{SEMR_2020_17_a68,
     author = {O. G. Parshina and M. A. Lisitsyna},
     title = {The perfect $2$-colorings of infinite circulant graphs with a continuous set of odd distances},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {590--603},
     publisher = {mathdoc},
     volume = {17},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2020_17_a68/}
}
TY  - JOUR
AU  - O. G. Parshina
AU  - M. A. Lisitsyna
TI  - The perfect $2$-colorings of infinite circulant graphs with a continuous set of odd distances
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2020
SP  - 590
EP  - 603
VL  - 17
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2020_17_a68/
LA  - en
ID  - SEMR_2020_17_a68
ER  - 
%0 Journal Article
%A O. G. Parshina
%A M. A. Lisitsyna
%T The perfect $2$-colorings of infinite circulant graphs with a continuous set of odd distances
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2020
%P 590-603
%V 17
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2020_17_a68/
%G en
%F SEMR_2020_17_a68
O. G. Parshina; M. A. Lisitsyna. The perfect $2$-colorings of infinite circulant graphs with a continuous set of odd distances. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 590-603. http://geodesic.mathdoc.fr/item/SEMR_2020_17_a68/

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

[2] S.V. Avgustinovich, M.A. Lisitsyna, “Perfect $2$-colorings of transitive cubic graphs”, J. Appl. Industr. Math., 5:4 (2011), 519–528 | DOI | MR

[3] 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 (Russian) | MR | Zbl

[4] M.A. 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

[5] D.G. Fon-Der-Flaass, “A bound on correlation immunity”, Siberian Electronic Mathematical Reports, 4 (2007), 133–135 | MR | Zbl

[6] D.G. Fon-Der-Flaass, “Perfect $2$-Colorings of a Hypercube”, Sibirsk. Mat. Zh., 48:4 (2007), 923–930 (Russian) | MR | Zbl

[7] D.G. Fon-Der-Flaass, “Perfect colorings of the 12-cube that attain the bound on correlation immunity”, Siberian Electronic Mathematical Reports, 4 (2007), 292–295 (Russian) | MR | Zbl

[8] A.L. Gavrilyuk, S.V. Goryainov, “On Perfect $2$-Colorings of Johnson Graphs $J(v,3)$”, J. Combin. Designs, 21:6 (2013), 232–252 | DOI | MR | Zbl

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

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

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

[12] D.S. Krotov, K.V. Vorob'ev, “On Unbalanced Boolean Functions with Best Correlation Immunity”, Electron. J. Combin., 27:1 (2020), 1–45 | DOI | MR | Zbl

[13] M.A. Lisitsyna, S.V. Avgustinovich, “Perfect colorings of the prism graph”, Siberian Electronic Mathematical Reports, 13 (2016), 1116–1128 (Russian) | MR | Zbl

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

[15] W.J. Martin, “Completely Regular Designs”, J. Combin. Designs, 6 (1998), 261–273 | 3.0.CO;2-D class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[16] I. Yu. Mogilnykh, Perfect $2$-colorings of Johnson graphs, PhD thesis, Novosibirsk, 2010 | Zbl

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

[18] O.G. Parshina, “Perfect $k$-colorings of infinite circulant graphs with a continuous set of distances”, Abs. Int. Conf. PhD Summer Sch. “Groups and Graphs, Algorithms and Automata” (Yekaterinburg, Russia, Aug. 9–15, 2015), 80 | MR

[19] S.A. Puzynina, Perfect colorings of infinite rectangular grid, PhD thesis, Novosibirsk, 2008 | MR

[20] 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

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

[22] K.V. Vorobev, D.G. Fon-Der-Flaass, “On perfect $2$-colorings of the hupercube”, Siberian Electronic Mathematical Reports, 7 (2010), 65–75 | MR