WorksComputer Science
Tight Bounds for Anonymous Parity Certification
Abstract
Local certification is the task of verifying graph properties using certificates assigned to vertices and checked using only local information. A central question is which properties admit constant-size certificates, independently of network size. A fundamental test case is the parity of the network order. Bousquet, Feuilloley, Valenzuela, and Zeitoun (DISC 2026) showed that the complexity of certifying even order depends dramatically on the verification model. On arbitrary graphs, three bits per vertex suffice with unique identifiers and verification radius two. In the anonymous radius-one model, they established an lower bound and an upper bound. They also showed that constant-size certificates suffice in this model on bounded-expansion classes. In this paper, we settle the complexity of anonymous parity certification on general graphs and further investigate the role of graph sparsity. Our main contributions are: * We close the gap left by Bousquet et al., proving that the local complexity of certifying even order in the anonymous radius-one model is bits. * We show that on graphs of degeneracy at most , parity can be certified with bits, while bits are necessary. In particular, every class of bounded degeneracy admits constant-size certificates, strictly generalizing the result for bounded-expansion classes. * We show that constant-size certification cannot be guaranteed on nowhere-dense classes, a broader notion of sparsity that includes bounded expansion. We construct a fixed, subgraph-closed nowhere-dense class on which parity certification requires bits. Together, our results provide a more complete picture of anonymous parity certification on sparse graph classes, showing that its complexity depends on the particular structural notion of sparsity.
Introduction
Local certification is a distributed mechanism for verifying graph properties. An all-powerful prover assigns a certificate to every vertex, and each vertex decides whether to accept by inspecting its local neighborhood and the certificates it contains. A scheme is correct if every graph satisfying the property has an assignment accepted everywhere, whereas on a graph violating it, every assignment is rejected by at least one vertex. The central resource is the maximum number of certificate bits per vertex; see [8, 12, 14, 18] for background. Recent research has increasingly focused on the constant-size regime: which properties can be certified with bits per vertex, independently of the size of the network? Such properties are sometimes regarded as “local” from the certification perspective, even when their definitions are global [1].
One of the most basic questions in this direction is whether the number of vertices is even. Let EVEN denote this property. Parity is inherently global: changing the number of vertices by one changes the answer, potentially far away from any given vertex. Yet it can be remarkably easy to certify. On cycles, even order is equivalent to bipartiteness and can be certified with one bit per vertex. On trees, constant-size certificates also suffice, by aggregating subtree sizes modulo two. The challenge is to understand whether such small local proofs are possible on arbitrary graphs.
This question was recently investigated by Bousquet, Feuilloley, Valenzuela, and Zeitoun [2] (DISC 2026), who uncovered a striking dependence on the verification model and the underlying graph class. On general graphs, they showed that three bits suffice when vertices have unique identifiers and the verification radius is two. At the other extreme, they studied the anonymous radius-one model, which corresponds to the MULTISET model of local verification. In this model, a vertex sees only its own certificate and the multiset of its neighbors’ certificates, including multiplicities, but has no identifiers, port numbers, or knowledge of the graph order. They proved an lower bound, against an upper bound. They also established that, on every graph class of bounded expansion, constant-size certificates suffice even in this restricted anonymous model. Bounded expansion is a robust notion of structural sparsity that includes, for example, bounded-degree and planar graphs.
Two natural questions remained. First, the gap between and left the actual complexity of anonymous parity certification on general graphs essentially undetermined. Second, the bounded-expansion result raised a structural question: how far can constant-size parity certification be extended beyond bounded expansion, and which weaker notions of sparsity, if any, still guarantee it? These are the questions we address here.
Our results
Our first contribution settles the open problem of [2] for anonymous networks with verification radius one. We establish matching upper and lower bounds on the size of the certificates.
Theorem 1. There is an anonymous radius-one certification scheme for EVEN using bits per vertex.
Our scheme shows that the order of the network need not be encoded explicitly to certify its parity, even in the anonymous radius-one model. The natural question is whether the doubly logarithmic dependence can be reduced further. We show that it cannot, already on connected bipartite graphs.
Theorem 2. For every sufficiently large even , there is a connected bipartite -vertex graph such that every accepting assignment of every correct anonymous radius-one verifier for
EVEN has a certificate of length . This remains true when correctness is required only on bipartite inputs.
Together, Theorems 1 and 2 show that certifying EVEN on connected -vertex graphs has local complexity . Thus parity has genuinely intermediate complexity in this model: constant-size certificates do not suffice, but the bits needed to explicitly represent the graph order are unnecessary. The lower bound holds even under a bipartite promise.
Our second contribution strengthens the positive result of [2] by replacing bounded expansion with bounded degeneracy. Recall that a graph is -degenerate if every nonempty subgraph has a vertex of degree at most . This condition allows vertices of arbitrarily large degree but restricts the density of every subgraph. Crucially, every bounded-expansion class has bounded degeneracy, whereas the converse is false: for example, the class of one-subdivisions of complete graphs is 2-degenerate but does not have bounded expansion.
Theorem 3. The verifier of Theorem 1 admits -bit certificates on every connected even-order -degenerate graph, for every integer , and constant-size certificates when . It remains sound on arbitrary connected graphs and is not supplied with .
In particular, every graph class of bounded degeneracy admits constant-size certificates, strengthening the bounded-expansion result of [2]. The dependence on , however, cannot be removed altogether. Our next result shows that the certificate size must grow with , even on bipartite graphs and even when the verifier is only required to work under the -degeneracy promise.
Theorem 4. For every sufficiently large integer , there is a connected bipartite graph of even order and degeneracy at most $d on which every accepting assignment of every anonymous radius-one certification scheme for EVEN contains a certificate of length . This holds even when correctness is required only on connected bipartite -degenerate graphs.
The two bounds leave a gap in the optimal dependence on the degeneracy parameter, between and .
Our third contribution shows that the bounded-expansion theorem cannot be extended to all nowhere-dense classes. A graph class is nowhere dense if, for every fixed radius , there is a clique that cannot occur as an -shallow minor of any graph in the class. This is a broad notion of sparsity: every bounded-expansion class is nowhere dense, but the converse does not hold, and nowhere-dense classes may have unbounded degeneracy.
Theorem 5. There exists a fixed, subgraph-closed nowhere-dense class of graphs on which certifying EVEN in the anonymous radius-one model has local complexity .
In fact, our construction gives a bipartite class whose girth grows with the graph order. A precise description of this class, together with a quantitative lower bound, is given in § 6. Thus, the full difficulty of the unrestricted anonymous model persists even on graphs with arbitrarily large girth.
Taken together, these results give a substantially sharper picture of parity certification on sparse graph classes. The constant-size result extends beyond bounded expansion to all classes of bounded degeneracy, but it fails already on a fixed nowhere-dense class. Hence the positive phenomenon discovered in [2] is not explained by sparsity in general: the particular structural restriction matters. What remains open is the exact quantitative cost of parity certification as a function of degeneracy.
Proof ideas and techniques
Sharing contributions without identifying parents. Earlier anonymous schemes organize contributions by choosing a parent for each vertex. A color identifies that parent only if no other neighbor has the same color [2]. Enforcing this uniqueness can require many colors, making the parent descriptions expensive.
Our approach allows a contribution to be shared among several neighbors. For example, two senders with the same two receivers can each send half a unit to each receiver. Each sender sends one unit in total, and each receiver receives one unit, even though neither sender distinguishes between the receivers. Fractions allow us to coordinate whole-number totals without making individual choices.
The verifier checks that the amount sent minus the amount received is an odd integer at every vertex. Every payment appears once as an outgoing amount and once as an incoming amount, so these differences sum to zero. Since an odd number of odd integers cannot sum to zero, acceptance implies that the graph has even order.
The main task is to arrange these payments using short descriptions. Our sharing lemma coordinates fractional payments so that receivers obtain integer totals, using colors and fractions that take bits to describe. The prover applies the lemma between successive distance layers, working toward a chosen root. At each step, a vertex chooses what to send according to the parity of what it has already received. On bounded-degeneracy graphs, the same construction uses constant-size descriptions.
Changing parity without changing local views. A lower bound construction must change the number of vertices; changing edges alone cannot change parity. It must also leave every vertex with a local view that the verifier accepts. The earlier construction [2] achieves this using all nonempty subsets of a point set, resulting in exponentially many vertices. We obtain a smaller construction using intervals in an ordered point set. Each interval is represented by a vertex adjacent to the points it contains.
The key is to find two collections of intervals that cover every point equally often, but whose numbers of intervals have different parities. If all their interval vertices carry the same certificate, we can copy one collection and delete the other. Every point loses and gains the same number of neighbors with that certificate. Retained interval vertices keep their views, and new copies imitate existing vertices. All checks still pass, although the graph order changes parity.
Intervals provide a simple way to find such collections. When traversing a closed loop of interval endpoints, rightward and leftward steps cover every point equally often. If the loop has odd length, the two groups of steps have different parities. Thus a sound verifier must prevent an odd cycle whose intervals all carry the same certificate. A classical coloring bound [16] then forces a logarithmic number of distinct certificates. Because the construction has only polynomially many vertices, describing that many certificates requires bits.
Preserving large girth through vertex splitting. For the nowhere-dense lower bound, we need a parity-changing operation that preserves large girth. Suppose three vertices carry the same certificate and one has a neighbor-certificate profile equal to the sum of the other two profiles. We can split that vertex into two, distributing its neighbors so that each replacement imitates one of the other vertices. Every old neighbor still sees one vertex with the original certificate. The order increases by one, and splitting cannot create a shorter cycle.
To force such a triple, we return to intervals. Their color-count profiles satisfy an exact identity: the profile of a long interval is the sum of the profiles of its two pieces. For every coloring of the point set, a counting argument finds an ordered sequence whose interval profiles are all sufficiently likely under random subset sampling. Sampling supplies many representatives of each profile, allowing us to remove short cycles while keeping all these representatives available. Color each interval’s endpoint pair by its representative’s certificate. An elementary Ramsey bound gives a monochromatic triangle, and hence the three equally certified profiles needed for splitting.
Related work
Sublogarithmic certification. Bousquet, Feuilloley, and Zeitoun [1] identified a regime for an arithmetic property of anonymous path lengths, defined using products of consecutive primes, and proved a gap between constant and logarithmic complexity on anonymous cycles. Our result brings the same intermediate scale to a simple counting predicate on unrestricted connected graphs. Since parity has constant-size certificates on paths and cycles, its difficulty here comes from the richer range of possible topologies. A related result of Feuilloley, Sedláček, and Slávik [11] gives -bit certificates for at most one selected vertex when the minimum degree is at least , for a sufficiently large constant . Their scheme uses identifiers and radius two, highlighting the different assumptions under which sublogarithmic certification becomes possible.
Structure and certificate size. Graph structure is a recurring theme in local certification, from certifying planarity [9] to logical metatheorems on tree-like graph classes [5, 10, 13]. On bounded-treewidth classes, these metatheorems progressed from -bit certificates [13] to -bit certificates for properties [5]. For parity in the anonymous radius-one model, Bousquet et al. [2] obtained constant-size certificates on bounded-expansion classes using Hickingbotham’s conflict-free neighborhood colorings [17]. We extend this constant-size guarantee from bounded expansion to bounded degeneracy. However, replacing bounded expansion with nowhere denseness does not preserve the guarantee: on a fixed subgraph-closed nowhere-dense class, parity certification still has the complexity of general graphs.
Combinatorial tools. Our construction draws on the theory of conflict-free and odd colorings [4, 6, 7, 20]. Conflict-free colors single out a neighbor, whereas odd colors need only occur an odd number of times in a neighborhood. Rational sharing adds another possibility: contributions can be distributed among indistinguishable neighbors while preserving integral totals. Conservation checks already appear in flow certification [18, 21]; the challenge here is to describe the transfers with short anonymous vertex certificates. The lower-bound techniques also have a broader reach. Chang, Lee, and Tsai [3] adapted the earlier parity construction to anonymous 2-vertex-connectivity, showing how neighborhood identities that preserve accepted local views can obstruct certification beyond counting predicates.
Discussion and open problems
We have determined the local complexity of EVEN in the anonymous radius-one model: bits are necessary and sufficient in the worst case. Parity thus gives an elementary global property whose optimal certificate size is unbounded but sublogarithmic. The two proofs explain this scale from complementary directions. Rational sharing coordinates parity contributions without selecting unique parents, while the interval construction quantifies how much ambiguity any sound verifier must eliminate. The same verifier admits constant-size certificates on every class of bounded degeneracy. These results settle the dependence on graph order and leave several questions about structure and the verification model.
The bound also holds, with a smaller leading constant in the lower bound, on a fixed subgraph-closed nowhere-dense class. Thus nowhere denseness alone does not guarantee constant-size certificates, even though bounded degeneracy does.
The dependence on degeneracy. Our structural bounds lie between and . They show that degeneracy alone controls certificate size, but do not determine the optimal dependence on this parameter.
Open problem 1. What is the optimal local complexity of certifying Even on connected -degenerate graphs, as a function of ? In particular, do -bit certificates suffice, independently of the graph order?
Our lower-bound witnesses have order , so the general upper bound already gives -bit certificates on them. Consequently, they cannot establish a larger asymptotic lower bound in terms of . An lower bound would require witnesses whose order exceeds every fixed polynomial in . Within our approach, improving the upper bound would require a more compact description of the sharing rules.
Identifiers and verification radius. Bousquet et al. [2] gave three-bit certificates when identifiers and radius two are both available. Our tight bound establishes the cost of imposing anonymity and radius one together. The intermediate cases, already asked about in [2], remain unresolved.
Open problem 2. What is the local complexity of certifying Even on arbitrary connected graphs (i) with identifiers and verification radius one, and (ii) anonymously with verification radius two? Do constant-size certificates suffice in either model?
Both models inherit our upper bound. The lower-bound modification uses anonymity to copy certified vertices without introducing new identifiers into their local views, and radius one to hide changes in their neighbors’ other incident edges. Extending the obstruction to either intermediate model therefore requires an additional idea. Resolving these cases would separate the roles of identifiers and observation radius in the cost of certifying parity.
Counting modulo other integers. Divisibility by a fixed integer, studied in [2], is a natural next setting in which to test the scope of our techniques.
Open problem 3. For a fixed integer , what is the optimal certificate size for verifying that the order of a connected graph is divisible by in the anonymous radius-one model? Does the bound hold for every such ?
The conservation principle extends directly: if every vertex has integer net outflow congruent to one modulo , then summing the balances forces . Constructing these balances with short anonymous labels, however, requires control of the residues modulo , beyond the odd–even distinction used here. For the lower bound, the profile-splitting construction also gives an lower bound for divisibility by every fixed integer , since it changes the order by exactly one. The remaining question is whether an upper bound holds for these moduli.
Model and definitions
Graphs and certification model
All graphs are finite, simple, and undirected; input graphs are connected. For , write , for the neighborhood of , , for the maximum degree, and for the subgraph induced by . We omit the subscript when clear. All logarithms are base two. Write and for the integers and rationals, and for the indicator of a condition or the characteristic vector of a set.
A graph is -degenerate, for an integer , if every nonempty subgraph has a vertex of degree at most . Equivalently, there is an ordering in which each vertex has at most later neighbors; the least such is its degeneracy. Orienting edges from earlier to later in this ordering gives an acyclic orientation of maximum outdegree at most .
The girth of a graph is the length of its shortest cycle, with girth infinity for forests. For an integer , a depth- minor of is obtained from a subgraph of by contracting pairwise disjoint connected subgraphs of radius at most , measured within each contracted subgraph. A graph class is nowhere dense if, for every integer , there is an integer such that no graph in contains as a depth- minor [19].
Certificates and local verification. We use the anonymous model with verification radius one of [2]. A certificate assignment on is a map , chosen by an external prover. The local view at a vertex is
where double braces denote a multiset. A verification algorithm is a deterministic function that takes this view and outputs accept or reject. The same function is used at every vertex and on every input graph. A graph is globally accepted if all its vertices accept. Vertices have no identifiers, ports, graph order, neighbor degrees, or information about edges between neighbors or their other incident edges. There are no computational restrictions on the prover or the verification function. In particular, the prover may assign different certificates to structurally indistinguishable vertices.
Certification schemes and local complexity. Let be a graph class, let be a graph property on , and let . A certification scheme for on with local complexity consists of a verification algorithm satisfying the following two conditions:
Completeness. Every connected -vertex graph satisfying admits a certificate assignment with for every vertex , under which is globally accepted.
Soundness. For every connected graph not satisfying , and every certificate assignment , at least one vertex rejects.
The class is a promise: the verification algorithm may depend on and , and no correctness requirement is imposed outside . Unless a class is specified, consists of all graphs. In this paper, : completeness concerns even-order graphs and soundness concerns odd-order graphs.
Rational transfers, encodings, and standard combinatorial facts
A transfer on an ordered edge contributes to the outgoing total at and the incoming total at . The net outflow is outgoing minus incoming; an odd net outflow means . All transfers used in the upper bounds are nonnegative rationals.
We fix a self-delimiting encoding of nonnegative integers. For , let be the binary length of and encode as , using bits. Encode a nonnegative rational by its numerator and positive denominator in lowest terms, with zero represented by . If has reduced denominator at most , its numerator is less than , so its encoding takes bits.
We use the following standard facts.
Lemma 6 (Hall [15]). Let be a finite bipartite graph, and write for . If for every , then has a matching covering .
Lemma 7 (Degeneracy bound, Szekeres and Wilf [22]). Every finite -degenerate graph has a proper coloring with at most colors.
Lemma 8 (Bipartite covers, Harary, Hsu, and Miller [16]). If bipartite subgraphs cover all edges of , then .
For a hypergraph , write for the maximum number of hyperedges containing a vertex, and for the minimum hyperedge size. A graph–hypergraph pair has a common vertex set.
Lemma 9 (Dai, Ouyang, and Pirot [6 Theorem 5]). There is a universal constant such that the following holds. Let be a finite graph–hypergraph pair, with . If , then its vertex set admits a coloring that is proper on and has some color occurring an odd number of times in each hyperedge of , using at most colors.
Upper bound in general graphs
Earlier anonymous schemes encode parents through conflict-free colors: a vertex selects a color unique among its predecessors [2]. This can be expensive even on sparse graphs. If there are receivers and one sender for every pair, all receivers need different colors. The resulting one-subdivision of has vertices, so color names take bits. Rational sharing avoids selecting a unique parent by allowing equal transfers to neighbors with the same color. We first construct transfers on a bipartite graph of senders and receivers, then apply this construction between consecutive BFS layers.
The sharing lemma
In a bipartite graph , vertices of are senders and vertices of are receivers. A receiver coloring is odd at a sender if some color occurs an odd number of times among its neighbors. Each sender stores a base amount and a selected color; each receiver stores its own color. These labels determine the edge transfers, including when senders have identical neighborhoods.
Lemma 10 (Sharing lemma). Let be a finite bipartite graph on vertices, with senders and receivers . Assume every sender has a neighbor. There are receiver colors , rational base amounts , and selected colors such that the transfers
satisfy
There are colors, each coordinate of a color is , and every base amount has reduced denominator . Each label , , or therefore has an -bit encoding, with color coordinates encoded separately. The value selects no color; equality of colors means equality in both coordinates, and no receiver color equals .
Proof. Let be the constant in Lemma 9. Take the least positive even integer , and put . Partition the senders into
We construct transfer rules for these two groups and then combine their receiver colorings.
Case 1: senders with at most neighbors. For each , write . Choose rational base amounts such that
Thus both outgoing and incoming base totals are integral. The zero assignment is feasible. Among feasible assignments, maximize the number of senders with odd outgoing base total. Call these senders satisfied, and the others unsatisfied. A maximum exists because this number is an integer between zero and .
We claim that the unsatisfied senders can be matched to distinct receivers. Otherwise Hall’s theorem gives a set of unsatisfied senders with . Their neighborhood vectors are supported on fewer coordinates than there are vectors, so they are linearly dependent over . Clearing denominators gives integers , not all zero, such that
Let be the positive greatest common divisor of the nonzero integers . Replace by for . At a receiver , the incoming total changes by . At sender , the outgoing total changes by the integer . These integers have greatest common divisor one, so at least one is odd. At least one previously even total becomes odd, and all previously satisfied senders are unchanged. This contradicts maximality. Hence there is a matching covering the unsatisfied senders; let be the receiver matched to . Figure 1 illustrates how a dependence preserves receiver totals while improving sender parities.

Figure 1. A rational perturbation in the maximality argument. All three senders have neighborhood , so the unsatisfied set in (a) violates Hall’s condition. Its neighborhood vectors admit the dependence ; since every sender has degree two, . Adding to the base amounts gives (b): each receiver’s incoming total is unchanged, but two senders become satisfied as their outgoing totals change from even to odd. Thus (a) cannot maximize the number of satisfied senders.
Subtract an even integer from each to put it in . All incoming and outgoing totals change by even integers, preserving integrality and parity. Since is integral, the reduced denominator of divides , and its numerator is less than . Thus the base amount takes bits.
To make a unit correction at each unsatisfied sender, form an auxiliary graph on the receivers. For every such sender , join to all other vertices of . For , every edge of is contributed by a matched receiver in . These receivers are distinct and each contributes at most edges, so
The graph is therefore -degenerate. Lemma 7 gives a proper coloring with colors. Each matched receiver has a color unique among its sender’s neighbors. Select this color at an unsatisfied sender, adding exactly one to its outgoing total. Select no color at a satisfied sender. Every sender in this case now sends an odd integer total, and receiver totals remain integral.
Case 2: senders with at least neighbors. Let be the hypergraph on whose hyperedges are the distinct neighborhoods , for . Set , taking if there are no hyperedges. A receiver belongs to at most one hyperedge per large sender, so .
If , the distinct neighborhoods are pairwise disjoint. Give one receiver in each such neighborhood color one and all remaining receivers color two. This is odd at every large sender; if there are no large senders, any coloring suffices.
If , apply Lemma 9 to the pair , where is the edgeless graph on the receivers. The parameters in the lemma satisfy
and the lemma supplies an odd coloring of with at most colors. Allowing unused colors, both cases therefore give a coloring that is odd at every sender in : each sender’s neighborhood is a hyperedge, including when several senders have the same neighbors.
Combining the receiver colorings. Give each receiver the ordered-pair color . This is a common refinement of the two colorings: two receivers have the same color precisely when they agree in both coordinates. There are at most color pairs. For a satisfied sender in , retain and set . For an unsatisfied sender, retain and select the refined color of . This receiver still has a color unique in , so all transfers from low-degree senders are unchanged.
For a sender in , an odd -color class in its neighborhood splits into refined color classes. At least one remains odd. Set and select that refined color as . This sends an odd integer total and contributes only integers at receivers. The low-degree senders already gave integral receiver totals, proving (1).
Every reduced denominator is at most ; its numerator is less than because . The two color coordinates are at most and , respectively, both . Encoding the coordinates separately, and using a constant-size tag to distinguish a selected pair from , gives bits for each color label. The rational bounds give the same bound for each base amount.
The certification scheme
Theorem 1. There is an anonymous radius-one certification scheme for EVEN using bits per vertex.
Proof. Certificate and verifier. A certificate is a four-tuple , where is a layer label, is a color, is a base amount, and is a selected color. Encode in two bits. Encode by concatenating the self-delimiting encodings of its two positive coordinates, using the integer encoding from the preliminaries. Record by its numerator and positive denominator in lowest terms, using the same integer encoding. Encode with a tag bit: 0 represents no selected color, and 1 is followed by the two encoded coordinates of the selected color. A certificate is malformed if its fields cannot be decoded, violate the stated ranges, record a fraction that is not in lowest terms, or leave unused trailing bits. Color equality is coordinatewise. Since no receiver color is 0, the selected color always means that no extra unit is sent.
For an arbitrary certificate assignment, call a neighbor of a predecessor when , and a successor when . Use subscripts to indicate the vertex supplying a field and write . A vertex rejects if any certificate in its local view is malformed. Otherwise it checks
The transfers are nonnegative rationals. The vertex computes its net outflow exactly and checks that it is an odd integer; a noninteger difference causes rejection. Both sums are computable from the local view: a neighbor’s fields determine its term, and repeated certificates contribute with their multiplicity. Three residues distinguish the two directions along consecutive layers; only these constant-size residues are stored, rather than full distances.
Soundness. Each transfer is counted once positively at its sender and once negatively at its receiver; edges between equal residues are ignored. This holds for arbitrary certificate assignments, regardless of whether the residues describe actual layers. If every vertex accepts, conservation gives
because each summand is an odd integer. Thus is even.
Completeness. Choose a root in an even-order graph and let
be its BFS layers. Give each vertex its layer number modulo three. Every edge joins equal or consecutive layers, and every nonroot vertex has a neighbor in the preceding layer.
Process , where is the maximum distance from the root; the root will be handled last. Once a vertex has received an integer amount from the next layer, its outgoing total must have parity opposite to . If is odd, set : the vertex sends zero, so its net outflow is odd. Call vertices with even active, and let be the active vertices of .
Form the bipartite graph with parts and , containing all edges of between these parts. Its senders are the active vertices and its receivers are the vertices of the preceding layer. It has at most vertices, and every sender has a receiver neighbor. If , apply Lemma 10 to : store its receiver colors on and its base amounts and selected colors on . On an edge of , its transfer is exactly the amount computed by the verifier. Every active vertex sends an odd integer total, and every vertex of receives an integer amount. This continues the induction, starting with zero incoming totals at the deepest layer. If , all transfers from that layer are zero and all vertices of the preceding layer may be given color . Any color not assigned by this procedure may be set to .
The color of a vertex is chosen when the next layer is processed; its base amount and selected color are chosen when its own layer is processed. Every nonroot vertex now has an odd integer net outflow: active vertices send an odd total after receiving an even total, and inactive vertices send zero after receiving an odd total. Give the root . All other checks already hold, so conservation forces its net outflow to be . This is an odd integer because is odd. This gives an accepting assignment.
Certificate size. By the sharing lemma, each color, base amount, and selected color can be encoded in bits. The layer label takes a constant number of bits. A fixed self-delimiting encoding preserves this asymptotic bound. Thus an anonymous radius-one verifier uses certificate bits. Figure 2 illustrates the construction, including fractional transfers and a unit correction.

Figure 2. Rational sharing on a six-vertex graph. In the first sharing step, the top vertices are senders and , are receivers; each sender is adjacent to both receivers. The orange edge adds one unit to the selected color; dashed edges carry zero. The integer receipts determine which receivers become active senders to the preceding layer. Every net outflow is odd, and their sum is zero.
Lower bound
The earlier lower bound [2] uses all nonempty subsets of an -point set, giving exponentially many vertices, and a finite-unions argument. We use only intervals, giving quadratically many vertices. An odd cycle of interval endpoints yields a parity-changing modification that preserves local views, and a bipartite-cover count then gives the quantitative certificate bound.
The interval incidence construction
For , take the ordered set of points . The graph has a point vertex for each and an interval vertex for every $0 \le i < j \le m$, adjacent exactly to . The corresponding subset of is the discrete interval . The endpoint indices $0,\ldots,m$ specify the boundaries of these intervals; they do not add vertices to . The graph is the bipartite incidence graph of these intervals: the two parts consist of point vertices and interval vertices. This graph is connected and bipartite, with vertices. When , its order is even. Indeed, is adjacent to every point vertex, and every other interval vertex has a nonempty set of point neighbors, proving connectedness.
Fix a sufficiently large even . Choose the largest with , and attach leaves to the point vertex . Call the resulting graph . It is connected and bipartite of order . Moreover , so and . These additional leaves give a graph for every sufficiently large even .
Consider any accepting certificate assignment on . Introduce a separate complete graph with vertex set , and color its edge by the certificate of . This auxiliary graph is not part of the input graph . Its vertices are the interval endpoints, whereas the two parts of represent points and intervals. The input graph remains bipartite even when the auxiliary graph contains odd cycles.
A modification preserving local views
The following lemma is the key local-view argument. A cycle of endpoints gives two collections of intervals that cover each point equally often, allowing additions and deletions of interval vertices to cancel at every point vertex.
Lemma 11. For every certificate , the subgraph of the auxiliary graph formed by the edges of color is bipartite.
Proof. Suppose that it contains a simple odd cycle . For its th edge, let if and if , and write
The interval vertices corresponding to these edges all have certificate . For , let ; in particular, . These vectors record the points at most . By the definition of and it holds that . Consequently
The differences sum to zero because each vector appears once with each sign as we go around the cycle. Call an interval positive if and negative if . Equation (3) says that each point is covered equally often by positive and negative intervals, even though their total number is odd. Figure 3 gives a five-cycle example.

Figure 3. An odd cycle gives a parity-changing modification. All five interval vertices have certificate . The traversal makes positive and negative. Delete and add the dashed copies . Each point vertex loses and gains one neighbor with certificate , while the order increases by one. Unshown vertices and edges are unchanged.
Modify the graph and its certificate assignment as follows. For every , delete the corresponding interval vertex. For every , add one new copy of that interval vertex, with certificate and the same point neighbors. Cycle edges are distinct, so the modifications are well defined. The resulting graph is still simple and bipartite: the copies are new vertices adjacent only to point vertices, even when their neighbor sets coincide with those of existing vertices.
At each point vertex, the change in the number of neighbors with certificate is zero by (3). All other neighbor-certificate multiplicities are unchanged. Its local view is therefore unchanged. Every retained interval vertex and every leaf added when constructing keeps its original local view. Each copy has the same local view as the vertex it copies. All vertices therefore accept.
The order changes by , which is odd because is odd. The modified graph thus has odd order. Some connected component has odd order and all its vertices still accept: taking a component changes no local view, and the verifier is not given the graph order. This contradicts soundness. There is therefore no odd cycle in the subgraph of color , so it is bipartite.
Counting certificates
Theorem 2. For every sufficiently large even , there is a connected bipartite -vertex graph such that every accepting assignment of every correct anonymous radius-one verifier for EVEN has a certificate of length . This remains true when correctness is required only on bipartite inputs.
Proof. Let be the number of distinct certificates on interval vertices. By the preceding argument, their endpoint color classes are bipartite subgraphs whose edge sets partition . Lemma 8 therefore gives . This invokes the classical counting bound; the local-view modification above is what makes it applicable to certificates. If all certificates in the assignment have length at most , then . Since , this yields
Bounds parameterized by degeneracy
We now prove bounds for certifying EVEN on -degenerate graphs. In the general construction, the description of a transfer depends on the order of the bipartite graph used at each layer. We replace this dependence by degeneracy. The key is that every graph between active vertices and their predecessors is a subgraph of the input graph. Its degeneracy is thus at most , even though a sender may have arbitrarily many receiver neighbors. The certificate format, BFS induction, and conservation check remain unchanged. For the lower bound, we check that the interval modification preserves the promised class.
Sharing on a -degenerate bipartite graph
The low-degree case of Lemma 10 already works with any prescribed degree bound. For senders of higher degree, degeneracy gives a receiver coloring with a unique color in each neighborhood, replacing the odd-coloring theorem used in the general proof.
Lemma 12. Let be an integer and let be a finite -degenerate bipartite graph, with senders and receivers . Assume every sender has a neighbor, and put . There are receiver colors , base amounts with reduced denominator at most , and selected colors such that
satisfies (1): every sender sends an odd integer total, and every receiver receives an integer total. Each label has an -bit encoding.
Proof. Partition the senders by degree:
Low-degree senders: reuse the rational construction. Apply the maximality and matching argument from Case 1 in the proof of Lemma 10, with degree bound , to . It gives rational base amounts with integer outgoing totals and integer incoming totals at all receivers. The reduced denominator divides and is therefore at most . The unsatisfied senders, whose outgoing base totals are even, have a matching to distinct receivers .
Keep the auxiliary graph joining each matched receiver to the other neighbors of , and postpone its coloring. The same counting argument gives
This part of the proof changes only the degree threshold.
High-degree senders: use degeneracy. Orient the whole graph in a degeneracy ordering, so every vertex has outdegree at most . This is an auxiliary orientation for choosing the colors; transfers will still go from senders to receivers, regardless of these directions. For , let . Given is -degenerate, at most edges leave in the auxiliary orientation, so at most of its receivers are outside . In particular, and since , it follows that . Each receiver belongs to at most of the neighborhoods , since each membership uses an edge leaving that receiver. These are the two consequences of degeneracy used in the construction: few exceptions at a sender, and bounded participation at a receiver. Figure 4 illustrates how the first bound ensures that a candidate color does not recur outside .

Figure 4. Ensuring a unique color when . In (a), the orientation has at most two edges leaving ; all other receivers lie in . The three blue candidates form . In (b), each candidate is adjacent in to every other receiver of , so a proper coloring makes its color unique there. The two exceptional receivers can repeat at most two candidate colors; the double-circled candidate retains a color unique in the whole neighborhood. Arrows in (a) show only the auxiliary orientation, not the direction of transfers.
For each , arbitrarily choose candidate receivers . Candidates may be shared by different senders. Form a graph on by joining each candidate in to every other receiver in , for every such . For ,
The first inequality bounds each sender’s contribution by stars on ; counting an edge repeatedly only increases the bound. The second uses the participation bound at receivers.
A common coloring and the transfers. Let . The two edge bounds give
Every nonempty induced subgraph has a vertex of degree at most . Lemma 7 therefore gives a proper coloring . Give each receiver the color to use the same ordered-pair format as in Lemma 10. This receiver coloring is proper on and uses at most color pairs.
For each satisfied sender in , set . For each unsatisfied one, select . The matched receiver has a color unique in , so this adds exactly one to the even outgoing base total.
For a sender in , its candidates have distinct colors, each occurring exactly once in . The at most exceptional receivers in can repeat at most of those colors. Hence one candidate still has a color unique among all neighbors of (see Figure 4). Set and select that color as . This sender sends exactly one unit.
All senders now have odd integer outgoing totals. Incoming totals remain integral because the low-degree base contributions were integral and all corrections are integers. There are color pairs, whose first coordinates are at most and whose second coordinates equal one. Each base amount has denominator at most and numerator less than . Encoding the color coordinates separately, with a tag for the selected color, gives bits for each label.
The upper bound and certificate size
Theorem 3. The verifier of Theorem 1 admits -bit certificates on every connected even-order -degenerate graph, for every integer , and constant-size certificates when . It remains sound on arbitrary connected graphs and is not supplied with .
Proof. Use exactly the certificate and verifier of Theorem 1. In particular, is not an input or a certificate field, and the verifier does not check degeneracy.
For completeness, choose BFS layers in a connected even-order -degenerate graph. Repeat the same induction from the deepest layer toward the root. At step , form the bipartite graph from the general construction: the active vertices of send to their neighbors in . Since is a subgraph of the input graph, it is -degenerate.
Apply Lemma 12 to in place of Lemma 10. Active vertices send odd integer totals; inactive vertices, having received odd integer totals, send zero. Each vertex of the preceding layer receives an integer total. The same induction gives odd integer net outflow at every nonroot vertex, and conservation gives an odd integer net outflow at the root because the graph has even order. As before, each vertex gets its receiver color when the next layer is processed, and its base amount and selected color when its own layer is processed.
The layer residue takes two bits. Each receiver color or selected color pair has first coordinate at most and second coordinate one; a selected color may also be 0. The rational numerator and denominator are . The fixed encoding of the certificate therefore takes bits in total, including the tag bit for the selected color. Soundness is unchanged: transfers cancel globally for arbitrary certificates, without any degeneracy assumption.
Both upper bounds use the same verifier and encoding. Consequently, on an -vertex even-order graph of degeneracy at most , this one verifier admits certificates of
bits. No scheme-selection field is needed: the prover may use either completeness construction, and neither nor is trusted input.
A lower bound within the degeneracy promise
The interval construction already has the appropriate degeneracy when its number of points is proportional to . To obtain a lower bound under a class promise, we must also ensure that the modification used against soundness stays within that class.
Theorem 4. For every sufficiently large integer , there is a connected bipartite graph of even order and degeneracy at most on which every accepting assignment of every anonymous radius-one certification scheme for Even contains a certificate of length . This holds even when correctness is required only on connected bipartite -degenerate graphs.
Proof. For a sufficiently large integer , let . Use the interval incidence graph from § 4; it is connected, bipartite and its order is even. Every interval vertex has degree at most . Deleting all interval vertices first and then the independent point vertices gives an -degeneracy ordering, so is -degenerate.
Fix a verifier correct on connected bipartite -degenerate graphs and any accepting assignment on . As in the general lower bound, color edge of the auxiliary by the certificate of . Each certificate class must be bipartite. Indeed, the argument in Lemma 11 turns an odd cycle of one color into interval deletions and copies that preserve every local view and change the parity of the order. The modified graph still has the same point vertices, and every interval vertex still has degree at most . The same deletion ordering proves that it remains -degenerate. Every connected component is thus bipartite and -degenerate. An odd-order component accepted everywhere would contradict soundness even within the promised class.
If distinct certificates occur on interval vertices, Lemma 8 gives . If all certificates have length at most , there are fewer than possible strings. Hence
where the asymptotic equality follows from . The argument applies to every accepting assignment and permits a different verifier for each fixed value of .
The witnesses have order and actual degeneracy . For , the first point vertices and the prefix interval vertices with induce . Thus their degeneracy is at least and at most . The lower bound therefore concerns the structural parameter itself, rather than an unnecessarily large upper estimate for it.
A lower bound on a nowhere-dense class
The bounded-degeneracy upper bound shows that many sparse classes admit constant-size certificates. We now show that the general bound remains tight on a fixed, subgraph-closed, bipartite nowhere-dense class.
Theorem 5. There exists a fixed, subgraph-closed nowhere-dense class of graphs on which certifying Even in the anonymous radius-one model has local complexity .
We now give a more explicit version of Theorem 5, identifying a concrete nowhere-dense class and providing a quantitative lower bound.
Lemma 13. Fix , and let
Then is subgraph-closed and nowhere dense. For every sufficiently large even , there is a connected -vertex graph such that, for every correct anonymous radius-one verifier for Even on , every accepting assignment on contains a certificate of length at least
Consequently, certifying Even on has local complexity .
We return to the interval idea from § 4, but use identities between color counts instead of identities between neighborhoods. This lets us change parity by splitting a single vertex, an operation that cannot create a shorter cycle.
For a certificate assignment using at most distinct strings, identify these strings with and define the profile
Thus the local view at is determined by and . The same formula defines when is defined only on a set containing . These colorings need not be proper.
Lemma 14. Let be a certificate assignment on a bipartite graph . Suppose that distinct vertices have the same certificate and
There are a simple bipartite graph of order and girth at least that of , and a certificate assignment on , such that every local view in occurs in .
Proof. Replace by two vertices , both carrying . Partition its neighbors within each certificate class so that has profile and has profile . This is possible by the assumed identity. The new vertices imitate and . Every retained vertex keeps its certificate and the number of its neighbors with each certificate, since any former neighbor of is adjacent to exactly one replacement carrying .
Put on the same side of the bipartition as . Identifying them back into maps any new cycle to a closed trail in : no edge repeats, since each old edge was assigned to exactly one replacement. The trail contains a cycle of no greater length, so girth does not decrease. The order increases by one. □
For example, profiles , , and allow the last vertex to be split into two vertices imitating the first two, provided all three carry the same certificate. If splitting disconnects the graph, every component still retains all its local views.
The next lemma supplies such a triple under every small certificate palette. Its property survives adding leaves at a vertex of , because none of the old neighborhoods on the side changes.
Lemma 15. There is an absolute constant such that, for all integers and , there is a connected bipartite graph of girth at least and order at most such that every coloring has distinct vertices with the same color and nonzero profiles satisfying
Here is the idea of the proof, deferred to Appendix § 7. An ordered sequence of points gives interval profiles satisfying the exact identity for . For each coloring of , a counting argument finds a sequence whose interval profiles all have a reasonable probability of appearing in random subsets. Sampling supplies many vertices with each of these profiles, simultaneously for all colorings, so deleting one set vertex from each short cycle still leaves every profile available. Select a representative for each interval and color its endpoint pair by the representative’s certificate. A monochromatic triangle gives the required three equally certified vertices. No approximation of color frequencies is needed. Figure 5 illustrates how the triangle gives the split.

Figure 5. A monochromatic triangle yields a split. The auxiliary edges , , in (a) have representatives , , with certificate 1 and profiles , , . Panels (b,c) show ’s actual neighborhood: and imitate and by receiving the two indicated groups. Every old neighbor still sees one vertex with certificate 1. Fills and numeric labels encode certificates. The templates are matched by color counts; their actual neighbors may differ. Unshown vertices and edges are unchanged.
Proof of Lemma 13. Taking a subgraph does not decrease girth or increase order, so is subgraph-closed. A depth- minor model of yields a cycle of length at most : join the endpoints of its three connecting edges inside their branch sets by paths of length at most each. These paths have disjoint interiors, since the branch sets are disjoint. For fixed , sufficiently large members of therefore exclude this minor. The remaining members have bounded order and exclude a sufficiently large complete minor. This proves nowhere denseness.
Fix a sufficiently large even , write , and choose
Then and . Since , Lemma 15 gives a graph with
Here the last equality uses . Thus for large . Add leaves at one vertex of until the order is exactly . The resulting connected graph lies in and retains the lemma’s profile property.
Suppose an accepting assignment on uses at most distinct certificates. Its restriction to gives equally certified vertices with . These are also their profiles in , since adding leaves at did not change their neighborhoods. Lemma 14 produces an accepted bipartite graph of odd order and girth at least . It has an odd-order component . This component is a connected accepted no-instance in the same promised class, since
This contradicts soundness on .
Every accepting assignment thus uses more than distinct strings. If their lengths are at most , then . Since ,
The upper bound follows from Theorem 1.
Together with Theorem 1, Lemma 13 implies Theorem 5.
AI disclosure
The writing of this paper and the derivation of its results were assisted by AI agents. We used Claude Code (Anthropic) with the model Claude Opus 5.5, and Codex (OpenAI) with the model GPT-6.1 Sol. The authors reviewed all text and results and take full responsibility for them.
Proof of Lemma 15
Proof. We need three equally colored vertices whose profiles satisfy an additive identity. Intervals provide the identity; a monochromatic triangle will provide the equal colors. The random construction only has to realize enough interval profiles to make this argument survive the removal of short cycles. Throughout the proof, denotes the natural logarithm.
Put
Let be a fixed set of points.
Every coloring has a sequence of likely interval profiles. Fix . For , let be the probability that a uniform -element subset of has profile . There are at most possible profiles, since each coordinate is an integer between 0 and . Consequently, a random -subset has a profile with with probability at most .
Now choose a uniform ordered sequence of distinct points. For each interval of positions, its points form a uniform -subset of . A union bound over fewer than intervals gives
Thus we can fix a sequence for which every interval profile , with , has probability at least under sampling a subset of its own size. Here is the th unit vector. These nonzero profiles satisfy
Fix one such sequence for each coloring of , before making the random graph. The sequence may depend on the coloring; the graph will work for all these choices simultaneously.
Realize the profiles, then remove short cycles. For every , independently sample uniform -element subsets of . Represent each sample by a new vertex adjacent to its elements. Repeated subsets give distinct vertices, so this incidence graph is simple and bipartite.
Fix a coloring of and one interval profile from its fixed sequence. The number of samples realizing that profile is binomial, with mean . Exponential Markov gives the elementary tail estimate
Indeed, for a binomial variable with trials and success probability , . There are colorings and fewer than fixed interval targets per coloring. Hence
Let count cycles of length less than . A cycle of length uses distinct points and distinct set vertices. There are at most ordered choices. A sampled set contains two specified distinct points with probability at most , and different set vertices were sampled independently. Therefore
By Markov, with probability at least . Some realization therefore has both properties. Delete one set vertex from each short cycle. At most vertices are deleted, leaving at least copies of every fixed interval target for every coloring of . All surviving set vertices keep their neighborhoods.
Every component contains a point. Connect the components along a tree by adding paths of length two between points in different components, with fresh internal vertices on the set side. The added edges are bridges. Thus girth is at least , and the surviving original set vertices still keep their profiles. The final graph is connected and has at most vertices.
A monochromatic triangle gives the split. Every edge coloring of with colors has a monochromatic triangle; this follows by induction on . It is immediate for . For , some vertex has at least neighbors joined to it in one color. Either that color occurs on an edge between those neighbors, completing a triangle, or their complete graph uses at most colors and induction applies.
Take any coloring of the whole constructed graph with at most colors, and use the sequence fixed for its restriction to . For every pair $0 \le i < j \le D$, choose a surviving original set vertex of profile . The representatives can be chosen distinct: fewer than are needed, while every target has at least available vertices. Color edge of the complete graph on by . The preceding Ramsey bound gives a monochromatic triangle . Its three representatives have the same color, and (6) gives . This is the required triple.
Finally,
The order bound is therefore at most for an absolute constant .
References
- [1]Nicolas Bousquet, Laurent Feuilloley, and Sébastien Zeitoun. Complexity landscape for local certification. In 39th International Symposium on Distributed Computing (DISC 2025), volume 356 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi: 10.4230/LIPIcs.DISC.2025.18.DOI
- [2]Nicolas Bousquet, Laurent Feuilloley, Jorge Valenzuela, and Sébastien Zeitoun. The local complexity of certifying parity, 2026. DISC 2026; full version.arxiv.org/abs/2606.04934
- [3]Yi-Jun Chang, Yi-Xuan Lee, and Meng-Tsung Tsai. Local certification of vertex and edge connectivity, 2026. URL https://arxiv.org/abs/2607.13677.
- [4]Panagiotis Cheilaris, Balázs Keszegh, and Dömötör Pálvölgyi. Unique-maximum and conflict-free coloring for hypergraphs and tree graphs. SIAM Journal on Discrete Mathematics, 27(4):1775–1787, 2013. doi: 10.1137/120880471.DOI
- [5]Linda Cook, Eun Jung Kim, and Tomáš Masarík. A tight meta-theorem for LOCAL certification of MSO₂ properties within bounded treewidth graphs. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC 2025), pages 110–120. ACM, 2025. doi: 10.1145/3732772.3733562.
- [6]Tianjiao Dai, Qiancheng Ouyang, and François Pirot. New bounds for odd colourings of graphs. The Electronic Journal of Combinatorics, 31(4):P4.57, 2024. doi: 10.37236/12110.DOI
- [7]Guy Even, Zvi Lotker, Dana Ron, and Shakhar Smorodinsky. Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. SIAM Journal on Computing, 33(1):94–136, 2003. doi: 10.1137/S0097539702431840.DOI
- [8]Laurent Feuilloley. Introduction to local certification. Discrete Mathematics & Theoretical Computer Science, 23(3), 2021. doi: 10.46298/dmtcs.6280.DOI
- [9]Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, and Ioan Todinca. Compact distributed certification of planar graphs. Algorithmica, 83 (7):2215–2244, 2021. doi: 10.1007/s00453-021-00823-w.DOI
- [10]Laurent Feuilloley, Nicolas Bousquet, and Théo Pierron. What can be certified compactly? compact local certification of MSO properties in tree-like graphs. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC 2022), pages 131–140. ACM, 2022. doi: 10.1145/3519270.3538416.DOI
- [11]Laurent Feuilloley, Josef Erik Sedláček, and Martin Slávik. Proving there is a leader without naming it, 2025. URL https://arxiv.org/abs/2511.15491.
- [12]Pierre Fraigniaud, Amos Korman, and David Peleg. Towards a complexity theory for local distributed computing. Journal of the ACM, 60(5):35:1–35:26, 2013. doi: 10.1145/2499228.DOI
- [13]Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. A meta-theorem for distributed certification. Algorithmica, 86(2):585–612, 2024. doi: 10.1007/s00453-023-01185-1.DOI
- [14]Mika Göös and Jukka Suomela. Locally checkable proofs in distributed computing. Theory of Computing, 12(19):1–33, 2016. doi: 10.4086/toc.2016.v012a019. URL https://theoryofcomputing.org/articles/v012a019/.DOI
- [15]Philip Hall. On representatives of subsets. Journal of the London Mathematical Society, s1-10(1):26–30, 1935. doi: 10.1112/jlms/s1-10.37.26.DOI
- [16]Frank Harary, Derbiau Hsu, and Zevi Miller. The biparticity of a graph. Journal of Graph Theory, 1(2):131–133, 1977. doi: 10.1002/jgt.3190010208.DOI
- [17]Robert Hickingbotham. Odd colourings, conflict-free colourings and strong colouring numbers. Australasian Journal of Combinatorics, 87(1):160–164, 2023. URL https://ajc.maths.uq.edu.au/pdf/87/ajc_v87_p160.pdf.arxiv.org/abs/2203.10402
- [18]Amos Korman, Shay Kutten, and David Peleg. Proof labeling schemes. Distributed Computing, 22(4):215–233, 2010. doi: 10.1007/s00446-010-0095-3.DOI
- [19]Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms, volume 28 of Algorithms and Combinatorics. Springer, 2012. doi: 10.1007/978-3-642-27875-4.DOI
- [20]János Pach and Gábor Tardos. Conflict-free colourings of graphs and hypergraphs. Combinatorics, Probability and Computing, 18(5):819–834, 2009. doi: 10.1017/S0963548309990290.DOI
- [21]Boaz Patt-Shamir and Mor Perry. Proof-labeling schemes: Broadcast, unicast and in between. Theoretical Computer Science, 923:179–195, 2022. doi: 10.1016/j.tcs.2022.05.006.
- [22]George Szekeres and Herbert S. Wilf. An inequality for the chromatic number of a graph. Journal of Combinatorial Theory, 4(1):1–3, 1968. doi: 10.1016/S0021-9800(68)80081-X.DOI