Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
417980 | Discrete Applied Mathematics | 2016 | 9 Pages |
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.