Publications - Published papers
Please find below publications of our group. Currently, we list 565 papers. Some of the publications are in collaboration with the group of Sonja Prohaska and are also listed in the publication list for her individual group. Access to published papers (
) is restricted to our local network and chosen collaborators.
If you have problems accessing electronic information, please let us know:
) is restricted to our local network and chosen collaborators.
If you have problems accessing electronic information, please let us know:©NOTICE: All papers are copyrighted by the authors; If you would like to use all or a portion of any paper, please contact the author.
Diagonalized Cartesian Products of S-prime graphs are S-prime
Marc Hellmuth, Lydia Gringmann, Peter F. Stadler
Download
Status: Published
Discrete Mathematics 312:74–80 (2012)
Abstract
A graph is said to be S-prime if, whenever it is a subgraph of a
nontrivial Cartesian product graph, it is a subgraph of one of the
factors. A diagonalized Cartesian product is obtained from a Cartesian
product graph by connecting two vertices of maximal distance by an
additional edge. We show there that a diagonalized product of S-prime
graphs is again S-prime. Klav{\v{z}}ar \emph{et al.}
[\emph{Discr.\ Math.} \textbf{244}: 223-230 (2002)] proved that a graph
is S-prime if and only if it admits a nontrivial path-$k$-coloring. We
derive here a characterization of all path-$k$-colorings of Cartesian
products of S-prime graphs.
Keywords
S-prime, diagonalized Cartesian product, path-k-coloring