Clique-width of countable graphs: A compactness property.

DOI10.1016/S0012-365X(03)00303-0zbMath1073.68062OpenAlexW2114915973MaRDI QIDQ1422417

No author found.

Publication date: 14 February 2004

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0012-365x(03)00303-0

zbMATH Keywords

Clique-widthCountable graph

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Decidability of theories and sets of sentences (03B25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (11)

Simple monadic theories and partition width ⋮ The relative clique-width of a graph ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ Inductive computations on graphs defined by clique-width expressions ⋮ Regularity Equals Monadic Second-Order Definability for Quasi-trees ⋮ Locality and modular Ehrenfeucht-Fraïssé games ⋮ Several notions of rank-width for countable graphs ⋮ The modular decomposition of countable graphs. Definition and construction in monadic second-order logic ⋮ Split permutation graphs ⋮ The monadic second-order logic of graphs. XV: On a conjecture by D. Seese ⋮ A model-theoretic characterisation of clique width

Cites Work

• Unnamed Item
• Unnamed Item
• The structure of the models of decidable monadic theories of graphs
• Fundamental properties of infinite trees
• Graph minors. I. Excluding a forest
• Graph minors. V. Excluding a planar graph
• Graph minors. X: Obstructions to tree-decomposition
• A partial k-arboretum of graphs with bounded treewidth
• The monadic second-order logic of graphs. X: Linear orderings
• The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic

This page was built for publication: Clique-width of countable graphs: A compactness property.