Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2017, 11:3, 381-388
Volume 24, No 3, 2017, P. 20-34
UDC 519.174.7
M. A. Lisitsyna and O. G. Parshina
Perfect colorings of the infinite circulant graph with distances 1 and 2
Abstract:
A coloring of the vertex set in a graph is called perfect if all its identically colored vertices have identical multisets of colors of their neighbors. Refer as the infinite circulant graph with continuous set of $n$ distances to the Cayley graph of the group $\mathbb Z$ with generator set{$1, 2, \dots , n$} . We obtain a description of all perfect colorings with an arbitrary number of colors of this graph with distances 1 and 2. In 2015, there was made a conjecture characterizing perfect colorings for the infinite circulant graphs with a continuous set of $n$ distances. The obtained result confirms the conjecture for $n = 2$. The problem is still open in the case of $n > 2$.
Bibliogr. 12.
Keywords: perfect coloring, circulant graph, equitable partition.
DOI: 10.17377/daio.2017.24.559
Mariya A. Lisitsyna 1
Olga G. Parshina 2,3
1. Marshal Budyonny Military Academy of Telecommunications,
3 Tikhoretsky Ave., 194064 St. Petersburg, Russia
2. Sobolev Institute of Mathematics,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
3. Institut Camille Jordan, Université Claude Bernard Lyon 1,
43 Boulevard du 11 Novembre 1918, F-69622 Villeurbanne Cedex, France
e-mail: lisicinama@ngs.ru, parolja@gmail.com
Received 2 December 2016
Revised 30 March 2017
References
[1] S. V. Avgustinovich, A. Yu. Vasil’eva, and I. V. Sergeeva, Distance regular colorings of the infinite rectangular grid, Diskretn. Anal. Issled. Oper., 18, No. 3, 3–10, 2011 [Russian]. Translated in J. Appl. Ind. Math., 6, No. 3, 280–285, 2012.[2] S. V. Avgustinovich and M. A. Lisitsyna, Perfect 2-colorings of transitive cubic graphs, Diskretn. Anal. Issled. Oper., 18, No. 2, 3–17, 2011 [Russian]. Translated in J. Appl. Ind. Math., 5, No. 4, 519–528, 2011.
[3] M. A. Lisitsyna, Perfect 3-colorings of prisms and Möbius ladders, Diskretn. Anal. Issled. Oper., 20, No. 1, 28–36, 2013 [Russian]. Translated in J. Appl. Ind. Math., 7, No. 2, 215–220, 2013.
[4] M. A. Lisitsyna and S. V. Avgustinovich, Perfect colorings of the prism graph, Sib. Electron. Mat. Izv., 13, 1116–1128, 2016 [Russian].
[5] O. G. Parshina, Perfect 2-colorings of infinite circulant graphs with continuous set of distances, Diskretn. Anal. Issled. Oper., 21, No. 2, 76–83, 2014 [Russian]. Translated in J. Appl. Ind. Math., 8, No. 3, 357–361, 2014.
[6] S. A. Puzynina, Perfect colorings of vertices of the graph $G(Z^2)$ in three colors, Diskretn. Anal. Issled. Oper., Ser. 2, 12, No. 1, 37–54, 2005 [Russian].
[7] D. B. Khoroshilova, On two-colour perfect colourings of circular graphs, Diskretn. Anal. Issled. Oper., 16, No. 1, 80–92, 2009 [Russian].
[8] D. B. Khoroshilova, On the parameters of perfect 2-colorings of circulant graphs, Diskretn. Anal. Issled. Oper., 18, No. 6, 82–89, 2011 [Russian].
[9] D. M. Cvetkovic, M. Doob, and H. Sachs, Spectra of Graphs: Theory and Application, VEB Dtsch. Verl. Wiss., Berlin, 1980. Translated under the title Spektry grafov: Teoriya i primenenie, Naukova Dumka, Kiev, 1984 [Russian].
[10] M. A. Axenovich, On multiple coverings of the infinite rectangular grid with balls of constant radius, Discrete Math., 268, No. 1–3, 31–48, 2003.
[11] O. G. Parshina, Perfect $k$-colorings of infinite circulant graphs with a continuous set of distances, in Abs. Int. Conf. PhD Summer Sch. “Groups and Graphs, Algorithms and Automata”, Yekaterinburg, Russia,
Aug. 9–15, 2015, p. 80, UrFU Publ., Yekaterinburg, 2015. Available at
http://g2a2.imm.uran.ru/doc/G2A2_Abstracts.pdf (accessed Apr. 16, 2017).
[12] S. A. Puzynina and S. V. Avgustinovich, On periodicity of two-dimensional words, Theor. Comput. Sci., 391, 178–187, 2008.
