Georgia Institute of Technology College of Sciences

A graph is chordal if each of its cycles of length at least four has a chord. Chordal graphs occupy an extreme end of a trade-off between structure and generalization: they have strong structure and admit many interesting characterizations, but this strong structure makes them a special case, representative of only a few graphs. In this talk, I'll discuss a new class of graphs called locally chordal graphs. Locally chordal graphs are more general than chordal graphs, but still have enough structure to admit interesting characterizations. In particular, most of the major characterizations of chordal graphs generalize to locally chordal graphs in natural and powerful ways. In addition to explaining these characterizations, I’ll discuss some ideas about how locally chordal graphs relate to new width parameters and to results in structural sparsity. This talk is based on joint work with Paul Knappe and Jonas Kobler.