|
On perfect colorings of paths divisible by a matching
M. A. Lisitsynaa, S. V. Avgustinovichb a Budyonny Military Academy of the Signal Corps, 3 Tikhoretsky Avenue, 194064 St. Petersburg, Russia
b Sobolev Institute of Mathematics, 4 Koptyug Avenue, 630090 Novosibirsk, Russia
Abstract:
A vertex coloring of a graph $G$ is called perfect if the color structure of the neighborhood of each vertex depends only on the color of this vertex. We give a complete characterization of perfect colorings with an arbitrary number of colors of the lexicographic product of the infinite path graph and the matching. Illustr. 1, bibliogr. 18.
Keywords:
perfect coloring, equitable partition, infinite path graph, matching, lexicographic product.
Received: 07.06.2021 Revised: 08.11.2021 Accepted: 29.11.2021
Citation:
M. A. Lisitsyna, S. V. Avgustinovich, “On perfect colorings of paths divisible by a matching”, Diskretn. Anal. Issled. Oper., 29:1 (2022), 33–45
Linking options:
https://www.mathnet.ru/eng/da1291 https://www.mathnet.ru/eng/da/v29/i1/p33
|
Statistics & downloads: |
Abstract page: | 189 | Full-text PDF : | 27 | References: | 50 | First page: | 10 |
|