Monochromatic Paths and Triangulated Graphs
Shimon Even, Ami Litman, Arnold L. Rosenberg · SIAM Journal on Discrete Mathematics · 1998
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, 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).