Publication detailsDabrowski, K.K. & Paulusma, D. (2014), Classifying the Clique-Width of H-Free Bipartite Graphs, in Cai, Zhipeng, Zelikovsky, Alexander & Bourgeois, Anu G. eds, Lecture Notes in Computer Science 8591: 20th International Conference, COCOON 2014. Atlanta, GA, USA, Springer, Atlanta GA, 489-500.
- Publication type: Conference Paper
- ISSN/ISBN: 0302-9743 (print), 1611-3349 (electronic), 978-3-319-08782-5 (print), 978-3-319-08783-2 (electronic)
- DOI: 10.1007/978-3-319-08783-2_42
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
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.