期刊
JOURNAL OF COMBINATORIAL THEORY SERIES B
卷 97, 期 1, 页码 91-126出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jctb.2006.04.003
关键词
clique-width; rank-width; monadic second-order logic; Seese's conjecture; local complementation; vertex-minor; isotropic system
类别
We prove that one can express the vertex-minor relation on finite undirected graphs by formulas of monadic second-order logic (with no edge set quantification) extended with a predicate expressing that a set has even cardinality. We obtain a slight weakening of a conjecture by Seese stating that sets of graphs having a decidable satisfiability problem for monadic second-order logic have bounded clique-width. We also obtain a polynomial-time algorithm to check that the rank-width of a graph is at most k for any fixed k. The proofs use isotropic systems. (c) 2006 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据