Daniel Cranston
DIMACS, Rutgers University and Bell Labs
Discharging And Reducibility: An Introduction By Example
Abstract:
Many coloring results and structural results on graphs are proved using a pair of techniques called reducibility and discharging. The most well-known such result is the 4-Color Theorem. More generally, to prove a hypothetical Theorem A for planar graphs, our proof has two phases: a discharging phase and a reducibility phase. In the discharging phase, we prove that every planar graph must contain at least one subgraph from a specified list. The name discharging comes from the fact that we assign a charge (an integer) to each vertex so the sum of the charges is negative; we move the charge around (discharge it) so that only vertices appearing in one of the specified subgraphs have negative charge. In the reducibility phase, we prove that any minimal counterexample to Theorem A cannot contain any subgraph in the specified list. This implies that there is no counterexample to Theorem A, and hence, the theorem is true.
In this talk, we illustrate the techniques of discharging and reducibility by proving the following theorem: The vertices of a planar graph of girth at least 14 can be partitioned into two subsets I and F such that G[F] is a forest and I is a 2-independent set, that is: any two vertices in I are distance more than 2 apart in G. This structural theorem has applications to star coloring; a star coloring is a proper coloring such that the union of any two color classes induces a forest of disjoint stars. This is joint work with Craig Timmons and Andre Kundgen, both of California State, San Marcos.