Clique-width of countable graphs: a compactness property Original Research Article

We define the clique-width of a countable graph. We prove that a countable graph has finite clique-width iff its finite induced subgraphs have bounded clique-width. We obtain an application to a conjecture concerning the structure of sets of countable graphs having a decidable monadic second-order satisfiability problem.