Classifying the clique-width of H-free bipartite graphs

被引：21

作者：

Dabrowski, Konrad K. ^{[1
]}

Paulusma, Daniel ^{[1
]}

机构：

[1] Univ Durham, Sch Engn & Comp Sci, Sci Labs, S Rd, Durham DH1 3LE, England

来源：

DISCRETE APPLIED MATHEMATICS | 2016年 / 200卷

基金：

英国工程与自然科学研究理事会;

关键词：

Clique-width; Bipartite graph; Graph class; CO-GEM-FREE; SET;

D O I：

10.1016/j.dam.2015.06.030

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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 no bipartition of G contains an induced copy of H in a way that respects the bipartition of H. Third, G is weakly H-free if G has at least one bipartition that does not contain an induced copy of H in a way that respects the bipartition of H. 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. (C) 2015 Elsevier B.V. All rights reserved.

引用

页码：43 / 51

页数：9

共 28 条

[11]

Brandstädt A, 2006, DISCRETE MATH THEOR, V8, P173

[12] Clique-width for 4-vertex forbidden subgraphs [J].

Brandstaedt, Andreas ;

Engelfriet, Joost ;

Le, Hoang-Oanh ;

Lozin, Vadim V. .

THEORY OF COMPUTING SYSTEMS, 2006, 39 (04) :561-590

[13] Linear time solvable optimization problems on graphs of bounded clique-width [J].

Courcelle, B ;

Makowsky, JA ;

Rotics, U .

THEORY OF COMPUTING SYSTEMS, 2000, 33 (02) :125-150

[14] Upper bounds to the clique width of graphs [J].

Courcelle, B ;

Olariu, S .

DISCRETE APPLIED MATHEMATICS, 2000, 101 (1-3) :77-114

[15]

Dabrowski Konrad Kazimierz, 2015, Language and Automata Theory and Applications. 9th International Conference, LATA 2015. Proceedings: LNCS 8977, P676, DOI 10.1007/978-3-319-15579-1_53

[16] Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs [J].

Dabrowski, Konrad K. ;

Paulusma, Daniel .

ALGORITHMS AND COMPLEXITY (CIAC 2015), 2015, 9079 :167-181

[17] Colouring of graphs with Ramsey-type forbidden subgraphs [J].

Dabrowski, Konrad K. ;

Golovach, Petr A. ;

Paulusma, Daniel .

THEORETICAL COMPUTER SCIENCE, 2014, 522 :34-43

[18]

Dabrowski KK, 2014, LECT NOTES COMPUT SC, V8591, P489, DOI 10.1007/978-3-319-08783-2_42

[19]

Gurski F., 2007, CORR

[20] Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs [J].

Heggernes, Pinar ;

Meister, Daniel ;

Papadopoulos, Charis .

DISCRETE APPLIED MATHEMATICS, 2012, 160 (06) :888-901

← 1 2 3 →