We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

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

Dabrowski, K.K. and Paulusma, D. (2016) 'Classifying the clique-width of H-free bipartite graphs.', Discrete applied mathematics., 200 . pp. 43-51.


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.

Item Type:Article
Keywords:Clique-width, Bipartite graph, Graph class.
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
Publisher Web site:
Publisher statement:© 2015 This manuscript version is made available under the CC-BY-NC-ND 4.0 license
Date accepted:22 June 2015
Date deposited:19 August 2015
Date of first online publication:15 July 2015
Date first made open access:15 July 2016

Save or Share this output

Look up in GoogleScholar