Publication detailsDabrowski, K.K. & Paulusma, D. (2016). Classifying the clique-width of H-free bipartite graphs. Discrete Applied Mathematics 200: 43-51.
- Publication type: Journal Article
- ISSN/ISBN: 0166-218X (print)
- DOI: 10.1016/j.dam.2015.06.030
- Keywords: Clique-width, Bipartite graph, Graph class.
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
Let GG be a bipartite graph, and let HH be a bipartite graph with a fixed bipartition (BH,WH)(BH,WH). We consider three different, natural ways of forbidding HH as an induced subgraph in GG. First, GG is HH-free if it does not contain HH as an induced subgraph. Second, GG is strongly HH-free if no bipartition of GG contains an induced copy of HH in a way that respects the bipartition of HH. Third, GG is weakly HH-free if GG has at least one bipartition that does not contain an induced copy of HH in a way that respects the bipartition of HH. Lozin and Volz characterized all bipartite graphs HH for which the class of strongly HH-free bipartite graphs has bounded clique-width. We extend their result by giving complete classifications for the other two variants of HH-freeness.