Output details
11 - Computer Science and Informatics
University of Leeds
A structure theorem for graphs with no cycle with a unique chord and its consequences
<13>Complete structure theorem is obtained, from which efficient algorithms are extracted. For coloring, novel technique is developed to make decomposition based algorithm work. Our structure theorem was subsequently used for complexity results for edge and total-coloring (Machado, de Figueiredo, Vušković 2010 and Machado, de Figueiredo 2011). This work enabled complete structural and algorithmic understanding of this class.
This paper is number 3 on the list of top cited papers of JGT 2010-2011 (and 22 JGT most cited across all 2004-10). Vušković presented this work as Invited Plenary Speaker at Oxford’s prestigious One-Day Meeting in Combinatorics (2009).
