Graphs with no long induced path

Abstract

In this thesis, we study graphs that do not contain long induced paths. We adapt a Ramsey-type theorem about infinite graphs that are traceable to a finite version: if a graph G contains a sufficiently long non-induced path with no short induced path, then G contains either a clique or a biclique. We also look at a bound for how large the non-induced path must be to guarantee the result. These graphs were studied in connection to the k-colorability problem for graphs with no long induced path.