M. A. Lisitsyna, S. V. Avgustinovich, “Perfect colorings of the prism graph”, Sib. Èlektron. Mat. Izv., 2016, Volume 13,Pages <nobr>1116

This article is cited in 8 papers

Discrete mathematics and mathematical cybernetics

Perfect colorings of the prism graph

M. A. Lisitsyna^a, S. V. Avgustinovich^b

^a Budyonny Military Academy of Telecommunications, Tikhoretsky pr., 3, 194064, St. Petersburg, Russia
^b Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia

Abstract: The cartesian product of an infinite chain by an edge is termed the infinite prism graph. A complete description of perfect colorings is obtained for prism graph. Bipartition of mentioned graph was used essentially by researchers. It's easy to adapt all results to finite case — finite prism graph and Mobius ladder.

Keywords: prism graph, Mobius ladder, perfect coloring, equitable partition, bipartite graph, induced coloring.

UDC: 519.174.7

MSC: 05C50

Received July 13, 2016, published December 8, 2016

DOI: 10.17377/semi.2016.13.088