Skip to main content

Research Repository

Advanced Search

Bounding clique-width via perfect graphs

Dabrowski, K. K.; Huang, S.; Paulusma, D.

Bounding clique-width via perfect graphs Thumbnail


Authors

K. K. Dabrowski

S. Huang



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 Mar 29, 2024
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





You might also like



Downloadable Citations