The (theta, wheel)-free graphs Part II: Structure theorem
- Submitting institution
-
The University of Leeds
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- UOA11-1133
- Type
- D - Journal article
- DOI
-
10.1016/j.jctb.2019.07.004
- Title of journal
- Journal of Combinatorial Theory, Series B
- Article number
- -
- First page
- 148
- Volume
- 143
- Issue
- -
- ISSN
- 0095-8956
- Open access status
- Compliant
- Month of publication
- August
- Year of publication
- 2019
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
2
- Research group(s)
-
A - AC (Algorithms and Complexity)
- Citation count
- 2
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- The (theta, wheel)-free graphs are a far generalization of chordal graphs. This series of papers generalizes a number of known results for chordal graphs to this class. We obtain a full structure theorem (which is quite rare). Consequently, polynomial-time recognition algorithm is obtained, resolving the last open question in much studied area of recognizing classes defined by excluding combinations of Truemper configurations (DOI:10.1016/j.jctb.2017.12.004 for survey). In DOI:10.1016/j.jctb.2019.07.003 the structure is used to design polynomial-time algorithms for clique, stable set and coloring problem on this class. Invited Plenary Speaker: BIRS Workshop (2017), 4th Scottish Combinatorics Meeting (2018), Bordeaux Graph Workshop (2019).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -
