Output details

Decomposition of even-hole-free graphs with star cutsets and 2-joins

<13>This paper (published in a top journal in combinatorics) significantly strengthens all previously known decompositions of even-hole-free graphs. It led to the fastest known recognition algorithm for this class by Chang and Lu in 2012. It is analogous to decomposition of Berge graphs by Chudnovsky, Robertson, Seymour and Thomas, which proved the famous Strong Perfect Graph Conjecture. The general techniques and insight that emerged from this work enabled Vušković to obtain structural and algorithmic understanding of other complex hereditary graph classes (in subsequent papers), leading to an invited chapter on this topic in Surveys in Combinatorics, LMS LNS (v409, 2013).

This type of work is usually done in larger teams of highly experienced individuals (e.g. Chudnovsky et al. above). Here Vušković tackled the problem effectively singlehandedly, while training PhD student da Silva. This paper was written by Vušković in intense 2 month bursts of writing about 20 pages of proofs each, with intermediate time spent on researching the overall structure of the next step. Completing the 95-page proof was Vušković's primary research effort for about two years. Note supplementary content available online.