Dabrowski, K.K. and Paulusma, D. (2014) 'Classifying the clique-width of H-free bipartite graphs.', in 20th International Conference, COCOON 2014, Atlanta, GA, USA, 4-6 August 2014 ; proceedings. Berlin, Heidelberg: Springer, pp. 489-500. Lecture notes in computer science. (8591).
Let G be a bipartite graph, and let H be a bipartite graph with a fixed bipartition (B H ,W H ). 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 G is H-free or else has no bipartition (B G ,W G ) with B H ⊆ B G and W H ⊆ W G . Third, G is weakly H-free if G is H-free or else has at least one bipartition (B G ,W G ) with TeX or TeX. 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.
|Item Type:||Book chapter|
|Full text:||(AM) Accepted Manuscript|
Download PDF (299Kb)
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-319-08783-2_42|
|Publisher statement:||The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-08783-2_42|
|Date accepted:||No date available|
|Date deposited:||15 January 2015|
|Date of first online publication:||2014|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|