Obstructions for linear rank-width at most 1

被引：12

作者：

Adler, Isolde ^{[1
]}

Farley, Arthur M. ^{[2
]}

Proskurowski, Andrzej ^{[2
]}

机构：

[1] Goethe Univ Frankfurt, Inst Informat, D-60325 Frankfurt, Germany

[2] Univ Oregon, Eugene, OR 97403 USA

来源：

DISCRETE APPLIED MATHEMATICS | 2014年 / 168卷

关键词：

Linear rank-width of graphs; Forbidden induced subgraphs; Obstruction set; Vector-minor; Pivot-minor; CLIQUE-WIDTH; GRAPHS; SET;

D O I：

10.1016/j.dam.2013.05.001

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We establish the set of minimal forbidden induced subgraphs for the class of graphs having linear rank-width at most I. From these we derive both the vertex-minor and pivot-minor obstructions for the class. (c) 2013 Elsevier B.V. All rights reserved.

引用

页码：3 / 13

页数：11

共 17 条

[1]

Adler Isolde, LNCS P WG 2 IN PRESS

[2] DISTANCE-HEREDITARY GRAPHS [J].

BANDELT, HJ ;

MULDER, HM .

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

[3] A partial k-arboretum of graphs with bounded treewidth [J].

Bodlaender, HL .

THEORETICAL COMPUTER SCIENCE, 1998, 209 (1-2) :1-45

[4] CIRCLE GRAPH OBSTRUCTIONS [J].

BOUCHET, A .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1994, 60 (01) :107-144

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

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

Courcelle, B ;

Olariu, S .

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

[7]

Diestel R., 1995, COMB PROBAB COMPUT, V4, P27

[8]

Espelage Wolfgang, 2001, Lecture Notes in Computer Science, V2204, P117, DOI DOI 10.1007/3-540-45477-2_12

[9]

Ganian R, 2011, LECT NOTES COMPUT SC, V6460, P38, DOI 10.1007/978-3-642-19222-7_5

[10]

Ganian R, 2009, LECT NOTES COMPUT SC, V5874, P266, DOI 10.1007/978-3-642-10217-2_27

← 1 2 →