Well-quasi-ordering versus clique-width
- Submitting institution
-
Birkbeck College
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 187
- Type
- D - Journal article
- DOI
-
10.1016/j.jctb.2017.09.012
- Title of journal
- Journal of Combinatorial Theory Series B
- Article number
- -
- First page
- 1
- Volume
- 130
- Issue
- -
- ISSN
- 0095-8956
- Open access status
- Compliant
- Month of publication
- October
- Year of publication
- 2017
- URL
-
http://eprints.bbk.ac.uk/id/eprint/20890/
- 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)
-
1 - Algorithms, Verification and Software
- Citation count
- 3
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Classes of graphs that are well quasi ordered (WQO) by the induced subgraph relation have been actively studied by graph theorists and theoretical computer scientists. An important open question relating to this topic is whether such classes have bounded cliquewidth (a parameter that would make many hard problems efficiently computable on these classes). It was widely believed that the answer was positive. In this paper we refute this belief and demonstrate a WQO class having unbounded cliquewidth thus settling this important open question.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -