Skip to main content

Research Repository

Advanced Search

Classifying the Clique-Width of H-Free Bipartite Graphs

Dabrowski, K. K. ; Paulusma, D.

Classifying the Clique-Width of H-Free Bipartite Graphs Thumbnail


Authors

K. K. Dabrowski



Contributors

Zhipeng Cai
Editor

Alexander Zelikovsky
Editor

Anu G. Bourgeois
Editor

Abstract

Let G be a bipartite graph, and let H be a bipartite graph with a fixed bipartition (B H ,W H ). We consider three different, natural ways of forbidding H as an induced subgraph in G. First, G is H-free if it does not contain H as an induced subgraph. Second, G is strongly H-free if G is H-free or else has no bipartition (B G ,W G ) with B H  ⊆ B G and W H  ⊆ W G . Third, G is weakly H-free if G is H-free or else has at least one bipartition (B G ,W G ) with TeX or TeX. Lozin and Volz characterized all bipartite graphs H for which the class of strongly H-free bipartite graphs has bounded clique-width. We extend their result by giving complete classifications for the other two variants of H-freeness.

Citation

Dabrowski, K. K., & Paulusma, D. (2014). Classifying the Clique-Width of H-Free Bipartite Graphs. In Z. Cai, A. Zelikovsky, & A. G. Bourgeois (Eds.), 20th International Conference, COCOON 2014, Atlanta, GA, USA, 4-6 August 2014 ; proceedings (489-500). https://doi.org/10.1007/978-3-319-08783-2_42

Conference Name 20th International Conference, COCOON 2014
Conference Location Atlanta, GA, USA
Publication Date Jan 1, 2014
Deposit Date Dec 20, 2014
Publicly Available Date Mar 28, 2024
Pages 489-500
Series Title Lecture notes in computer science
Series Number 8591
Series ISSN 0302-9743,1611-3349
Book Title 20th International Conference, COCOON 2014, Atlanta, GA, USA, 4-6 August 2014 ; proceedings.
ISBN 9783319087825
DOI https://doi.org/10.1007/978-3-319-08783-2_42
Public URL https://durham-repository.worktribe.com/output/1153880

Files





You might also like



Downloadable Citations