You are in : Home » Results & submissions » Select UOA » 11 - Computer Science and Informatics » View submission: University of Leeds » Outputs » Detail

Output details

11 - Computer Science and Informatics

University of Leeds

Return to search Previous output Next output

Output 36 of 95 in the submission

Article title

Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences

Type

D - Journal article

DOI

10.1016/j.jctb.2008.12.005

Title of journal

Journal of Combinatorial Theory, Series B

Article number

Volume number

Issue number

First page of article

733

ISSN of journal

0095-8956

Year of publication

2009

URL

Number of additional authors

Additional information

<13>Even-hole-free graphs are studied because they relate to (beta-)perfect graphs. We substantially strengthen known methods to decompose (even-hole,diamond)-free graphs. This enables us to prove that these graphs are beta-perfect. Only now one can apply all known results on beta-perfect graphs to (even-hole,diamond)-free graphs. This paper was the most downloaded article from JCT(B) in the month it appeared:

http://top25.sciencedirect.com/subject/mathematics/16/journal/journal-of-combinatorial-theory-series-b/00958956/archive/23/.

Subsequently, Vušković and da Silva extended our decomposition to all even-hole-free graphs (analogously to the famous decomposition of perfect graphs), leading to the fastest known recognition algorithm for that class (2012).

Interdisciplinary

Cross-referral requested

Research group

None

Citation count

Proposed double-weighted

Double-weighted statement

Reserve for a double-weighted output

Non-English

English abstract