Using the Potential Method to Color Near-Bipartite Graphs 08/30/19

Speaker: Dan Cranston, VCU
Date and time: Friday, August 30, 4–5pm
Place: Rome 771

Abstract: A graph $G$ is near-bipartite if we can partition $V(G)$ as $(I,F)$ where $I$ is an independent set and $F$ induces a forest. Similar to the problem of 3-coloring, deciding whether a graph is near-bipartite is NP-hard. Thus, we seek sufficient conditions. We show that a multigraph $G$ is near-bipartite if $3|W|-2|E(G[W])|\ge -1$ for every $W\subseteq V(G)$ , and $G$ contains no $K_4$ and no Moser spindle. We show that a simple graph $G$ is near-bipartite if $8|W|-5|E(G[W])|\ge -4$ for every $W\subseteq V(G)$ and $G$ contains no subgraph in some finite family (each member of which is not near-bipartite). Each result is very sharp. Namely, if we weaken the lower bound in either hypothesis by 1, then the resulting statement is false infinitely often.

Both results are proved using the potential method, a powerful technique for coloring sparse graphs. As a consequence, both theorems lead to polynomial-time algorithms to find the desired partition. This is joint work with Matthew Yancey.