Coloring perfect graphs with no balanced skew-partitions
- Submitting institution
-
The University of Leeds
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- UOA11-1131
- Type
- D - Journal article
- DOI
-
10.1016/j.jctb.2015.04.007
- Title of journal
- Journal of Combinatorial Theory, Series B
- Article number
- -
- First page
- 26
- Volume
- 115
- Issue
- -
- ISSN
- 0095-8956
- Open access status
- Out of scope for open access requirements
- Month of publication
- April
- Year of publication
- 2015
- 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
-
3
- Research group(s)
-
A - AC (Algorithms and Complexity)
- Citation count
- 6
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- In 2011 interview (part-17 of https://www.simonsfoundation.org/science_lives_video/laszlo-lovasz/), Lásló Lovász , one of the most famous researchers in Combinatorics and TCS, identified the problem of finding combinatorial poly-time algorithm for optimally coloring perfect graphs as one of the three most interesting (still) open problems he has worked on.
We obtain such algorithm for perfect graphs with no balanced skew-partition, by developing techniques for using 2-joins and their generalizations in algorithms. These cutsets appear naturally in decomposition of different hereditary-graph classes, so the techniques developed in this paper for their use in algorithms are bound to have wider impact (evidence e.g. in DOI:10.1016/j.jctb.2019.07.003).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -
