MONOCHROMATIC PATHS AND TRIANGULATED

Technical Report CS0854

TR#:	CS0854
Class:	CS
Title:	MONOCHROMATIC PATHS AND TRIANGULATED GRAPHS.
Authors:	S. Even, A. Litman and A. Rosenberg
PDF	CS0854.pdf
Abstract:	This paper considers two properties of graphs, one geometrical and one topological, and shows that they are strongly related. Let $G$ be a graph with four distinguished and distinct vertices, $w_1,w_2,b_1,b_2$. Consider the two properties, $TRI^+(G)$ and $MONO(G)$, defined as follows: $TRI^+(G)$: There is a planar drawing of $G$ such that: all 3-cycles of $G$ are faces; all faces of $G$ are triangles except for the single face which is the 4-cycle $(w_1-b_1-w_2-b_2-w_1)$. $MONO(G)$: $G$ contains the 4-cycle $(w_1-b_1-w_2-b_2-w_1)$, and for any labeling of the vertices of $G$ by the colors {white, black}, such that $w_1$ and $w_2$ are white, while $b_1$ and $b_2$ are black, {\em precisely one} of the following holds. There is a path of white vertices connecting $w_1$ and $w_2$. There is a path of black vertices connecting $b_1$ and $b_2$. Our main result is that a graph $G$ enjoys property $TRI^+(G)$ if, and only if, it is minimal with respect to property $MONO$. Building on this, we show that one can decide in polynomial time whether or not a given graph $G$ has property $MONO(G)$.
Copyright	The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1995/CS/CS0854), rather than to the URL of the PDF files directly. The latter URLs may change without notice.