2

When you make deductions in this coloring problem you are following paths in the dual graph to the triangulation. Any inconsistency could be described by a cycle in the dual graph (a cycle of triangles linked edge-to-edge in the given maximal planar graph) such that, when you color one of the triangles (it doesn't matter which one or which coloring) and then ...


2

I think there's a straightforward transformation to graphs with colored edges, which can in turn be transformed into ordinary graphs. Given a CNF $\phi$ with clauses $c_i$ and variables $v_i$, construct a graph with vertices $c_i,v_i,\neg v_i$. Add black edges between each clause $c_i$ and each literal in it. Add a red edge between each variable $v_i$ and ...


1

There is a polynomial time algorithm for this problem. First, as pointed out by D.W., by Hall's theorem we can assume that there is a perfect matching between $A$ and $B$. In particular, if there is no perfect matching then there is a subset $S$ with $|S| > |N(S)|$, and we can remove vertices from $S$ without affecting $N(S)$ until we get an answer. Now ...


Only top voted, non community-wiki answers of a minimum length are eligible