Stable cuts and NAC-colorings

Abstract

It is known that a flexible realization of a graph in the plane exists if and only if the graph has a so called NAC-coloring, which is an edge coloring by two colors such that every cycle is either monochromatic or it has at least two blue and two red edges. We prove that a minimally rigid graph has a NAC-coloring, and hence also a flexible realization, if and only if the graph is not a 2-tree. The main ingredience of the proof is the characterization of the graphs with n vertices and $2n-3$ edges that have no stable cut by Le and Pfender, where a stable cut is a set of vertices inducing no edges such that its removal disconnects the graph. We strengthen to all flexible graphs the result by Chen and Yu stating that every graph with at most $2n-4$ edges has a stable cut. We also study the bounds on the number of NAC-colorings for various classes of graphs. This is joint work with K. Clinch, D. Garamvölgyi, J. Haslegrave, T. Huynh and A. Nixon.