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.
|Keywords:||Clique-width, Bipartite graph, Graph class.|
|Full text:||(AM) Accepted Manuscript|
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF (402Kb)
|Publisher Web site:||http://dx.doi.org/10.1016/j.dam.2015.06.030|
|Publisher statement:||© 2015 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/|
|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|