White Rose University Consortium logo
University of Leeds logo University of Sheffield logo York University logo

Even-hole-free graphs

Da Silva, Murilo Vicente Gonçalves (2008) Even-hole-free graphs. PhD thesis, University of Leeds.


Download (890Kb)


In this thesis we consider the class of simple graphs defined by excluding even holes (i.e. chordless cycles of even length). These graphs are known as even-hole-free graphs. We first prove that every even-hole-free graph has a node whose neighborhood is triangulated. This implies that in an even-hole-free graph, with n nodes and m edges, there are at most n+2m maximal cliques. It also yields a fastest known algorithm for computing a maximum clique in an even-hole-free graph. Afterwards we prove the main result of this thesis. The result is a decomposition theorem for even-hole-free graphs, that uses star cutsets and 2-joins. This is a significant strengthening of the only other previously known decomposition of even-hole-free graphs, by Conforti, Cornu´ejols, Kapoor and Vuˇskovi´c, that uses 2-joins and star, double star and triple star cutsets. It is also analogous to the decomposition of Berge (i.e. perfect) graphs with skew cutsets, 2-joins and their complements, by Chudnovsky, Robertson, Seymour and Thomas. In a graph that does not contain a 4-hole, a skew cutset reduces to a star cutset, and a 2-join in the complement implies a star cutset, so in a way it was expected that even-hole-free graphs can be decomposed with just the star cutsets and 2-joins. A consequence of this decomposition theorem is an O(n19) recognition algorithm for even-hole-free graphs. The recognition of even-hole-free graphs was first shown to be polynomial by Conforti, Cornu´ejols, Kapoor and Vuˇskovi´c. They obtained an algorithm of complexity of about O(n40) by first preprocessing the input graph using a certain “cleaning” procedure, and then constructing a decomposition based recognition algorithm. The cleaning procedure was also the key to constructing a polynomial time recognition algorithm for Berge graphs. At that time it was observed by Chudnovsky and Seymour that once the cleaning is performed, one does not need a decomposition based algorithm, one can instead just look for the “bad structure” directly. Using this idea, as opposed to using the decomposition based approach, one gets significantly faster recognition algorithms for Berge graphs and balanced 0,±1 matrices. However, this approach yields an O(n31) recognition algorithm for even-hole-free graphs. So this is the first example of a decomposition based algorithm being significantly faster than the Chudnovsky/Seymour style algorithm.

Item Type: Thesis (PhD)
Additional Information: Supplied directly by the School of Computing, University of Leeds.
Academic Units: The University of Leeds > Faculty of Engineering (Leeds) > School of Computing (Leeds)
Identification Number/EthosID: uk.bl.ethos.487716
Depositing User: Dr L G Proll
Date Deposited: 28 Mar 2011 10:05
Last Modified: 07 Mar 2014 11:23
URI: http://etheses.whiterose.ac.uk/id/eprint/1357

You do not need to contact us to get a copy of this thesis. Please use the 'Download' link(s) above to get a copy.
You can contact us about this thesis. If you need to make a general enquiry, please see the Contact us page.

Actions (repository staff only: login required)