Coloring square-free Berge graphs
- Submitting institution
-
The University of Leeds
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- UOA11-1132
- Type
- D - Journal article
- DOI
-
10.1016/j.jctb.2018.07.010
- Title of journal
- Journal of Combinatorial Theory, Series B
- Article number
- -
- First page
- 96
- Volume
- 135
- Issue
- -
- ISSN
- 0095-8956
- Open access status
- Compliant
- Month of publication
- September
- Year of publication
- 2018
- 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
-
4
- Research group(s)
-
A - AC (Algorithms and Complexity)
- Citation count
- 1
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- The combinatorial coloring algorithm obtained in this paper involved substantially strengthening the known decomposition theorem for Berge graphs (DOI:10.4007/annals.2006.164.51), and then using a particular recoloring technique on vertex cutset used.
An article about this paper appeared in Quanta Magazine (an online publication launched by the Simons Foundation to enhance public understanding of science): https://www.quantamagazine.org/20151020-perfect-graph-coloring/
This paper was also crucial for securing a new EPSRC grant (EP/N019660/1) that continues this successful line of research.
Several invited talks were given on this work, e.g. Vuškovic presented this result as Invited Plenary Speaker at Workshop on Structure in Graphs and Matroids, Eindhoven 2016.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -
