On perfect colorings of infinite multipath graphs

DOI10.33048/SEMI.2020.17.139zbMATH Open1453.05062arXiv2003.06803OpenAlexW3113671413MaRDI QIDQ2227017FDOQ2227017

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)

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.

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

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

zbMATH Keywords

equitable partitionperfect coloringequivalent colorsinnite multipath graph

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Compact graphs and equitable partitions
• On periodicity of two-dimensional words
• On circular perfect two-color colorings
• Title not available (Why is that?)
• On periodicity of perfect colorings of the infinite hexagonal and triangular grids
• Perfect colorings of vertices of the graph \(G(Z^2)\) in three colors
• Weight Distribution of Translates of Linear Codes and Generalized Pless Indentities
• Perfect colorings of the infinite circulant graph with distances 1 and 2
• The perfect 2-colorings of infinite circulant graphs with a continuous set of odd distances
• Perfect colorings of the prism graph
• Perfect 2-colorings of infinite circulant graphs with continuous set of distances
• Satisfying neighbor preferences on a circle

Cited In (13)

• Title not available (Why is that?)
• Perfect colorings of the infinite circulant graph with distances 1 and 2
• Title not available (Why is that?)
• Perfect 2-colorings of infinite circulant graphs with continuous set of distances
• On lexicographic colorings and some perfect graphs
• On perfect colorings of paths divisible by a matching
• On perfect colorings of line graphs
• On circular perfect two-color colorings
• New perfect colorings of infinite circulant graphs with continuous sets of distanses
• The perfect 2-colorings of infinite circulant graphs with a continuous set of odd distances
• Algebraic properties of perfect structures
• Perfect colorings of the infinite square grid: coverings and twin colors
• Colorings of infinite graphs without one-colored rays

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)