On perfect colorings of infinite multipath graphs

DOI10.33048/SEMI.2020.17.139MaRDI QIDQ2227017zbMATH OpenOpenAlexFDO

Authors Mariya Aleksandrovna Lisitsyna, Sergey Avgustinovich, Olga G. Parshina

Publication date 9 February 2021

Published in Sibirskie Elektronnye Matematicheskie Izvestiya (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.06803

zbMATH Keywords

equitable partitionperfect coloringequivalent colorsinnite multipath graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: A coloring of vertices of a given graph is called perfect if the color structure of each ball of radius $1$ in the graph depends only on the color of the ball 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.

Recommendations

• On perfect colorings of paths divisible by a matching
• Perfect colorings of the infinite circulant graph with distances 1 and 2
• On circular perfect two-color colorings
• Perfect 2-colorings of infinite circulant graphs with continuous set of distances
• Perfect colorings of radius \(r>1\) of the infinite rectangular grid

Cites work

• scientific article; zbMATH DE number 6007921 (Why is no real title available?)
• scientific article; zbMATH DE number 2097450 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• scientific article; zbMATH DE number 2232233 (Why is no real title available?)
• Compact graphs and equitable partitions
• On circular perfect two-color colorings
• On periodicity of perfect colorings of the infinite hexagonal and triangular grids
• On periodicity of two-dimensional words
• Perfect 2-colorings of infinite circulant graphs with continuous set of distances
• Perfect colorings of the infinite circulant graph with distances 1 and 2
• Perfect colorings of the prism graph
• Perfect colorings of vertices of the graph \(G(Z^2)\) in three colors
• Satisfying neighbor preferences on a circle
• The perfect 2-colorings of infinite circulant graphs with a continuous set of odd distances
• Weight Distribution of Translates of Linear Codes and Generalized Pless Indentities

Cited in

(13)

• Perfect colorings of the infinite square grid: coverings and twin colors
• Colorings of infinite graphs without one-colored rays
• New perfect colorings of infinite circulant graphs with continuous sets of distanses
• scientific article; zbMATH DE number 6712803 (Why is no real title available?)
• On perfect colorings of paths divisible by a matching
• Perfect colorings of the infinite circulant graph with distances 1 and 2
• On perfect colorings of line graphs
• The perfect 2-colorings of infinite circulant graphs with a continuous set of odd distances
• Perfect 2-colorings of infinite circulant graphs with continuous set of distances
• On lexicographic colorings and some perfect graphs
• Algebraic properties of perfect structures
• On circular perfect two-color colorings
• scientific article; zbMATH DE number 3902684 (Why is no real title available?)

This page was built for publication: On perfect colorings of infinite multipath graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2227017)