### Forbidden Subgraphs and 3-Colorability

- Series
- Dissertation Defense
- Time
- Monday, May 21, 2012 - 14:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Tianjun Ye – School of Mathematics, Georgia Tech

Classical vertex coloring problems ask for the minimum number of colors needed
to color the vertices of a graph, such that adjacent vertices
use different colors. Vertex coloring does have quite a few practical applications
in
communication theory, industry engineering and computer science. Such examples can
be
found in the book of Hansen and Marcotte.
Deciding whether a graph is 3-colorable or not is a well-known NP-complete problem,
even for triangle-free graphs. Intutively, large girth may help reduce the chromatic
number.
However, in 1959, Erdos used the probabilitic method to prove that for any two
positive
integers g and k, there exist graphs of girth at least g and chromatic number at
least k.
Thus, restricting girth alone does not help bound the chromatic number. However, if
we
forbid certain tree structure in addition to girth restriction, then it is possible
to bound the
chromatic number. Randerath determined several such tree structures, and conjectured
that
if a graph is fork-free and triangle-free, then it is 3-colorable, where a fork is a
star K1,4
with two branches subdivided once.
The main result of this thesis is that Randerath's conjecture is true for graphs
with odd
girth at least 7. We also give an outline of a proof that Randerath's conjecture
holds for
graphs with maximum degree 4.