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

Title: Using the Potential Method to Color Near-Bipartite Graphs

Abstract: A graph is *near-bipartite* if we can partition as where is an independent set and 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 is near-bipartite if for every , and contains no and no Moser spindle. We show that a simple graph is near-bipartite if for every and 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.