Vertex-minors, monadic second-order logic, and a conjecture by Seese

Cited 43 time in webofscience Cited 0 time in scopus
  • Hit : 263
  • Download : 0
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.
Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
Issue Date
2007-01
Language
English
Article Type
Article
Keywords

GRAPH MINORS; CLIQUE-WIDTH; BRANCH-WIDTH; ISOTROPIC SYSTEMS; RANK-WIDTH; TREE-WIDTH; MATROIDS; SETS; OBSTRUCTIONS; RECOGNITION

Citation

JOURNAL OF COMBINATORIAL THEORY SERIES B, v.97, no.1, pp.91 - 126

ISSN
0095-8956
DOI
10.1016/j.jctb.2006.04.003
URI
http://hdl.handle.net/10203/90616
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 43 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0