MONOCHROMATIC PATHS AND TRIANGULATED GRAPHS

This paper considers two properties of graphs, one geometrical and one topological, and shows that they are strongly related. Let G be a gra ph 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 foll ows. TRI+ (G): There is a planar drawing of G such that all 3-cycles o f 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 - contain s - 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 b1 and b2 are black, precisely one of the following holds. There is a path of white vertices connecting w(1) and w(2). The re is a path of black vertices connecting b(1) and b(2). Our main resu lt is that a graph G enjoys property TRI+ (G) if and only if it is min imal 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 prop erty MONO(G).