Diagonalized Cartesian Products of S-prime graphs are S-prime

Abstract

A graph is said to be View the MathML source-prime if, whenever it is a subgraph of a nontrivial Cartesianproductgraph, it is a subgraph of one of the factors. A diagonalizedCartesianproduct is obtained from a Cartesianproductgraph by connecting two vertices of maximal distance by an additional edge. We show there that a diagonalizedproduct of View the MathML source-primegraphs is again View the MathML source-prime. Klavžar et al. [S. Klavžar, A. Lipovec, M. Petkovšek, On subgraphs of Cartesianproductgraphs, Discrete Math. 244 (2002) 223–230] proved that a graph is View the MathML source-prime if and only if it admits a nontrivial path-k-coloring. We derive here a characterization of all path-k-colorings of Cartesianproducts of View the MathML source-primegraphs.

Citation

[HGS12] Hellmuth, M., Gringmann, L., Stadler, P.F. (2012). Diagonalized Cartesian Products of S-prime graphs are S-prime, Discrete Mathematics, 312, 1, 74-80, 2012
Read Publication