Classifying the clique-width of H-free bipartite graphs

Let  G be a bipartite graph, and let  H be a bipartite graph with a fixed bipartition (BH,WH). 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 no bipartition...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2016-02, Vol.200, p.43-51
Main Authors: Dabrowski, Konrad K., Paulusma, Daniël
Format: Article
Language:English
Subjects:
Bipartite graph
Clique-width
Graph class
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let  G be a bipartite graph, and let  H be a bipartite graph with a fixed bipartition (BH,WH). 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 no bipartition of  G contains an induced copy of  H in a way that respects the bipartition of  H. Third, G is weakly H-free if  G has at least one bipartition that does not contain an induced copy of  H in a way that respects the bipartition of  H. 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.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2015.06.030