  A proof-labeling scheme (PLS) for a boolean predicate $\Pi$ on labeled graphs
is a mechanism used for certifying the legality with respect to $\Pi$ of global
network states in a distributed manner. In a PLS, a certificate is assigned to
each processing node of the network, and the nodes are in charge of checking
that the collection of certificates forms a global proof that the system is in
a correct state, by exchanging the certificates once, between neighbors only.
The main measure of complexity is the size of the certificates. Many PLSs have
been designed for certifying specific predicates, including cycle-freeness,
minimum-weight spanning tree, planarity, etc.
  In 2021, a breakthrough has been obtained, as a meta-theorem stating that a
large set of properties have compact PLSs in a large class of networks. Namely,
for every $\mathrm{MSO}_2$ property $\Pi$ on labeled graphs, there exists a PLS
for $\Pi$ with $O(\log n)$-bit certificates for all graphs of bounded
tree-depth. This result has been extended to the larger class of graphs with
bounded {tree-width}, using certificates on $O(\log^2 n)$ bits.
  We extend this result even further, to the larger class of graphs with
bounded clique-width, which, as opposed to the other two aforementioned
classes, includes dense graphs. We show that, for every $\mathrm{MSO}_1$
property $\Pi$ on labeled graphs, there exists a PLS for $\Pi$ with $O(\log^2
n)$ bit certificates for all graphs of bounded clique-width.
