Classifying the clique-width of H-free bipartite graphs

Dabrowski, K.K.; Paulusma, D.

Abstract

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.

Citation

Dabrowski, K., & Paulusma, D. (2016). Classifying the clique-width of H-free bipartite graphs. Discrete Applied Mathematics, 200, 43-51. https://doi.org/10.1016/j.dam.2015.06.030

• Journal Article Type: Article
• Acceptance Date: Jun 22, 2015
• Online Publication Date: Jul 15, 2015
• Publication Date: Feb 19, 2016
• Deposit Date: Aug 12, 2015
• Publicly Available Date: Jul 15, 2016
• Journal: Discrete Applied Mathematics
• Print ISSN: 0166-218X
• Electronic ISSN: 1872-6771
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 200
• Pages: 43-51
• DOI: https://doi.org/10.1016/j.dam.2015.06.030
• Keywords: Clique-width, Bipartite graph, Graph class.
• Public URL: https://durham-repository.worktribe.com/output/1404212