Combinatorics Seminar- Using the Potential Method to Color Near-Bipartite Graphs

Fri, 30 August, 2019 8:00pm

Speaker: Dan Cranston, VCU

Date and Time: Friday, August 30 4–5 pm

Place: Rome 771

Title: Using the Potential Method to Color Near-Bipartite Graphs
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.