RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2022 Volume 29, Issue 1, Pages 33–45 (Mi da1291)

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.

UDC: 519.174.7

Received: 07.06.2021
Revised: 08.11.2021
Accepted: 29.11.2021

DOI: 10.33048/daio.2022.29.718



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025