Clique-width with an inactive label

被引：3

作者：

Meister, Daniel ^{[1
]}

机构：

[1] Univ Trier, D-54286 Trier, Germany

来源：

DISCRETE MATHEMATICS | 2014年 / 337卷

关键词：

Clique-width; Linear clique-width; Characterisation; Forbidden induced subgraphs; Distance-hereditary graphs; RANK-WIDTH; NLC-WIDTH; GRAPHS;

D O I：

10.1016/j.disc.2014.08.005

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

An inactive label in a clique-width expression cannot be used to create edges, and vertices that are labelled inactive have already received their incident edges. We study properties of clique-width expressions with inactive labels. The main results are: a characterisation of the distance-hereditary graphs by their clique-width expressions, a characterisation of the linear clique-width of disconnected graphs, and the complete set of disconnected minimal graphs of linear clique-width at least 4. (C) 2014 Elsevier B.V. All rights reserved.

引用

收藏

页码：34 / 64

页数：31

相关论文

共 25 条

[1] Obstructions for linear rank-width at most 1 [J].

Adler, Isolde ;

Farley, Arthur M. ;

Proskurowski, Andrzej .

DISCRETE APPLIED MATHEMATICS, 2014, 168 :3-13

[2]

Adler I, 2013, LECT NOTES COMPUT SC, V8165, P12, DOI 10.1007/978-3-642-45043-3_3

[3] DISTANCE-HEREDITARY GRAPHS [J].

BANDELT, HJ ;

MULDER, HM .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1986, 41 (02) :182-208

[4]

Brignall R., 2013, CORR

[5] Claw-free graphs. III. Circular interval graphs [J].

Chudnovsky, Maria ;

Seymour, Paul .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2008, 98 (04) :812-834

[6] Polynomial-time recognition of clique-width ≤ 3 graphs [J].

Corneil, Derek G. ;

Habib, Michel ;

Lanlignel, Jean-Marc ;

Reed, Bruce ;

Rotics, Udi .

DISCRETE APPLIED MATHEMATICS, 2012, 160 (06) :834-865

[7] COMPLEMENT REDUCIBLE GRAPHS [J].

CORNEIL, DG ;

LERCHS, H ;

BURLINGHAM, LS .

DISCRETE APPLIED MATHEMATICS, 1981, 3 (03) :163-174

[8] 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

[9] HANDLE-REWRITING HYPERGRAPH GRAMMARS [J].

COURCELLE, B ;

ENGELFRIET, J ;

ROZENBERG, G .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1993, 46 (02) :218-270

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

Courcelle, B ;

Olariu, S .

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