Skip to main content

Research Repository

Advanced Search

Classifying the clique-width of H-free bipartite graphs

Dabrowski, K.K.; Paulusma, D.

Classifying the clique-width of H-free bipartite graphs Thumbnail


Authors

K.K. Dabrowski



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
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

Files





You might also like



Downloadable Citations