K. K. Dabrowski
Bounding clique-width via perfect graphs
Dabrowski, K. K.; Huang, S.; Paulusma, D.
Authors
Contributors
Adrian-Horia Dediu
Editor
Enrico Formenti
Editor
Carlos Martín-Vide
Editor
Bianca Truthe
Editor
Abstract
Given two graphs H1 and H2, a graph G is (H1,H2)-free if it contains no subgraph isomorphic to H1 or H2. We continue a recent study into the clique-width of (H1,H2)-free graphs and present three new classes of (H1,H2)-free graphs that have bounded clique-width. We also show the implications of our results for the computational complexity of the Colouring problem restricted to (H1,H2)-free graphs. The three new graph classes have in common that one of their two forbidden induced subgraphs is the diamond (the graph obtained from a clique on four vertices by deleting one edge). To prove boundedness of their clique-width we develop a technique based on bounding clique covering number in combination with reduction to subclasses of perfect graphs.
Citation
Dabrowski, K. K., Huang, S., & Paulusma, D. (2015). Bounding clique-width via perfect graphs. In A. Dediu, E. Formenti, C. Martín-Vide, & B. Truthe (Eds.), Language and automata theory and applications : 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015 ; proceedings (676-688). https://doi.org/10.1007/978-3-319-15579-1_53
Conference Name | International Conference on Language and Automata Theory and Applications |
---|---|
Conference Location | Nice, France |
Start Date | Mar 2, 2015 |
End Date | Mar 6, 2015 |
Publication Date | Feb 24, 2015 |
Deposit Date | Dec 20, 2014 |
Publicly Available Date | Feb 24, 2016 |
Pages | 676-688 |
Series Title | Lecture notes in computer science |
Series Number | 8977 |
Series ISSN | 0302-9743 |
Book Title | Language and automata theory and applications : 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015 ; proceedings. |
ISBN | 9783319155784 |
DOI | https://doi.org/10.1007/978-3-319-15579-1_53 |
Keywords | Clique-width, Forbidden induced subgraphs, Graph class. |
Public URL | https://durham-repository.worktribe.com/output/1154558 |
Files
Accepted Conference Proceeding
(434 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-15579-1_53.
You might also like
Solving Infinite-Domain CSPs Using the Patchwork Property
(2023)
Conference Proceeding
Disjunctive Temporal Problems under Structural Restrictions
(2021)
Conference Proceeding
Fine-Grained Complexity of Temporal Problems
(2020)
Conference Proceeding
Independent transversals versus transversals
(2019)
Conference Proceeding
Filling the complexity gaps for colouring planar and bounded degree graphs
(2019)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search