  Given a network property or a data structure, a local certification is a
labeling that allows to efficiently check that the property is satisfied, or
that the structure is correct. The quality of a certification is measured by
the size of its labels: the smaller, the better.This notion plays a central
role in self-stabilization, because the size of the certification is a lower
bound (and often an upper bound) on the memory needed for silent
self-stabilizing construction of distributed data structures. From the point of
view of distributed computing in general, it is also a measure of the locality
of a property (e.g. properties of the network itself, such as planarity).
  When it comes to the size of the certification labels, one can identify three
important regimes: the properties for which the optimal size is polynomial in
the number of vertices of the graph, the ones that require only polylogarithmic
size, and the ones that can be certified with a constant number of bits. The
first two regimes are well studied, with several upper and lower bounds,
specific techniques, and active research questions. On the other hand, the
constant regime has never been really explored, at least on the lower bound
side. The main contribution of this paper is the first non-trivial lower bound
for this low regime. More precisely, we show that by using certification on
just one bit (a binary certification), one cannot certify $k$-colorability for
$k\geq 3$. To do so, we develop a new technique, based on the notion of score,
and both local symmetry arguments and a global parity argument. We hope that
this technique will be useful for establishing stronger results. We complement
this result by a discussion of the implication of lower bounds for this
constant-size regime, and with an upper bound for a related problem,
illustrating that in some cases one can do better than the natural upper bound.
