Graphs and Matroids Seminar - Paul Wollan

Title: Excluding a ladder

Abstract:

A folklore result says that if a graph does not contain the path of length k as a subgraph, then it has tree-depth at most k. One way of defining tree-depth is through the minimum number of colors needed for a centered coloring of the graph. A centered coloring is a proper coloring such that on each connected subgraph, some color is used exactly once. We will discuss an extension of this idea of centered colorings of graphs and how it relates to the maximum length of a ladder minor in the graph as well as further consequences of excluding a ladder minor.