Technical Report CS0854

TR#:CS0854
Class:CS
Title: MONOCHROMATIC PATHS AND TRIANGULATED GRAPHS.
Authors: S. Even, A. Litman and A. Rosenberg
PDFCS0854.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)$.
CopyrightThe 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.

To the list of the CS technical reports of 1995
To the main CS technical reports page

Computer science department, Technion
admin