Classifying the Clique-Width of H-Free Bipartite Graphs

Dabrowski, K. K. ; Paulusma, D.

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, December). Classifying the Clique-Width of H-Free Bipartite Graphs. Presented at 20th International Conference, COCOON 2014, Atlanta, GA, USA

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 20th International Conference, COCOON 2014
• Publication Date: Jan 1, 2014
• Deposit Date: Dec 20, 2014
• Publicly Available Date: Jan 15, 2015
• Print ISSN: 0302-9743
• 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