Lech Adamus

Edge condition for long cycles in bipartite graphs

Keywords: bipartite graph, cycle, long cycle, bipancyclicity, edge condition, size condition

The following problem was solved by Woodall in 1972: for any pair of nonnegative integers n and k < n 2 -1 find the minimum integer g(n, k) such that every graph with n vertices and at least g(n, k) edges contains a cycle of length n -k. Woodall proved even more: the size g(n, k), in fact, guarantees the existence of cycles Cp for all 3 ≤ p ≤ n -k.

In the paper an analogous problem for bipartite graphs is considered. It is proved that every bipartite graph with color classes of cardinalities m and n, m ≤ n, and size greater than n(m -k -1) + k + 1 contains a cycle of length 2m -2k, where m ≥ 1 2 k 2 + 3 2 k + 4, k ∈ N. The bound on the number of edges is best possible. Moreover, this size condition guarantees the existence of cycles of all even lengths up to 2m -2k. We also characterize all extremal graphs for this problem. Finally, we conjecture that the condition on the order may be relaxed to m ≥ 2k + 2.

Introduction

We will consider only finite, undirected graphs without loops and multiple edges. For the standard terminology and notation see e. g. [START_REF] Diestel | Graph Theory[END_REF].

Let G be a graph with the vertex set V (G) and the edge set E(G). Denote by |G| the number of vertices in G, which is the order of G, and by ||G|| the number of edges in G, which is the size of G.

In 1961, Ore proved the following theorem.

Theorem 1 (Ore [START_REF] Ore | Arc coverings of graphs[END_REF]) Let G be a graph with |G| = n and ||G|| ≥ 1 2 (n -1)(n -2) + 2. Then G contains a hamiltonian cycle.

It is natural to generalize the above problem as follows: for any pair of nonnegative integers n and k < n 2 -1, find the minimum integer g(n, k), such that every graph of order n and size at least g(n, k) contains a cycle of length nk.

In 1972, Woodall found the number g(n, k) and, what's more, proved that any graph of size at least g(n, k) contains cycles of all lengths up to nk.

Theorem 2 (Woodall [START_REF] Woodall | Sufficient conditions for circuits in graphs[END_REF]) Let G be a graph with |G| = n ≥ 2k + 3, k ∈ N, and

||G|| ≥ g(n, k) = n -k -1 2 + k + 2 2 + 1.
Then G contains a cycle of length p for each p such that 3 ≤ p ≤ nk.

This result is best possible. A graph consisting of two cliques, one on nk -1 vertices and the other one on k + 2 vertices, which share one vertex, is an extremal graph for this problem. It does not contain any cycle of length nk and it has exactly g(n, k) -1 edges.

We wish to investigate an analogous problem for bipartite graphs. Let G = (X, Y ; E) denote a bipartite simple graph with color classes X and Y and the set of edges E. Such a graph G is called balanced if X and Y have equal cardinalities.

For x ∈ V (G) we denote by N G (x) the set of neighbors of the vertex x in G, and by d G (x) the degree of the vertex x in G, so that d G (x) = |N G (x)|. The minimal vertex degree in G will be denoted by δ(G).

For A ⊂ V (G) and x ∈ V (G) we define e(x, A) = |N G (x) ∩ A|. We write G -A for the subgraph of G induced by V (G) \ A.
An xypath is a path with endvertices x and y, and C k (resp. P k ) denotes a cycle (resp. path) of order k. The balanced bipartite graph G = (X, Y ; E) is hamiltonian biconnected if for any two vertices x ∈ X and y ∈ Y , there exists a hamiltonian xy-path in G. It is 2-hamiltonian biconnected if for any pair of vertices a ∈ X and b ∈ Y, the subgraph G -{a, b} is hamiltonian biconnected. A graph G is said to be bipancyclic if it contains cycles of all even lengths up to |G|.

The aim of this paper is to find the minimum number of edges of a bipartite graph G = (X, Y ; E) on m + n vertices (|X| = m ≤ n = |Y |), which guarantees the existence of a cycle of length 2m -2k in G, for any integer 0 ≤ k < m 2 -1. We prove that, for m ≥ 1 2 k 2 + 3 2 k + 4, this extremal number of edges is equal to n(mk -1) + k + 2 and this size, in fact, guarantees the existence of cycles of all even lengths up to 2m -2k in G. Our result is a generalization of the following theorems.

Theorem 3 (Mitchem and Schmeichel [START_REF] Mitchem | Pancyclic and bipancyclic graphs -a survey, Graphs and applications[END_REF]) Let G = (X, Y ; E) be a balanced bipartite graph of order 2n

(|X| = |Y | = n). If ||G|| ≥ n 2 -n + 2, then G is bipancyclic.
Theorem 4 (Bagga and Varma [START_REF] Bagga | Hamiltonian properties in bipartite graphs[END_REF])

Let G = (X, Y ; E) be a bipartite graph with |X| = m ≤ n = |Y |. If ||G|| ≥ n(m -1) + 2, then G contains cycles C 2p for all 2 ≤ p ≤ m.
We also characterize all extremal graphs of size n(mk -1) + k + 1 that do not contain any cycle of length 2m -2k.

The main result of this paper (Theorem 5) and its proof are presented in Section 2. A version for balanced bipartite graphs of this theorem was first announced in [START_REF] Adamus | Long cycles in graphs and digraphs[END_REF]. In Section 3 we formulate a conjecture which is a stronger form of Theorem 5.

Main theorem

First we introduce a family of extremal graphs. For any three integers m, n and k, where 2 ≤ m ≤ n and

0 ≤ k ≤ m -2, we define the family G m,n,k of bipartite graphs G = (X, Y ; E) with |X| = m, |Y | = n, such that X = A ∪ B, |B| = k + 1, d G (v) = n for every v ∈ A and d G (w) = 1
for every w ∈ B (see Figure 1). Note that every graph of the family G m,n,k has size equal to n(mk -1) + k + 1 and does not contain any cycle of length 2m -2k. Moreover, if we add any edge to a graph of G m,n,k , then it will contain a cycle Our purpose is to prove the following theorem.

C 2m-2k . m-k-1 n X Y k+1 k+1 vertices of degree 1
Theorem 5 Let G = (X, Y ; E) be a bipartite graph with |X| = m ≤ n = |Y |, where m ≥ 1 2 k 2 + 3 2 k+4, k ∈ N. If ||G|| ≥ f (m, n, k) = n(m -k -1) + k + 1, then either G contains a cycle of length 2m -2k, or else ||G|| = f (m, n, k) and G is isomorphic to a graph of the family G m,n,k . In both cases G contains C 2p for all 2 ≤ p ≤ m -k -1.
In the course of the proof of Theorem 5, we shall use the following results.

Theorem 6 (Bagga and Varma [START_REF] Bagga | Hamiltonian properties in bipartite graphs[END_REF]) Let G = (X, Y ; E) be a balanced bipartite graph of order 2n. If for every pair of nonadjacent vertices x ∈ X and y

∈ Y, d G (x) + d G (y) ≥ n + 1, then G is bipancyclic.
Theorem 7 (Amar, Favaron, Mago and Ordaz [START_REF] Amar | Biclosure and bistability in a balanced bipartite graph[END_REF]) Let G = (X, Y ; E) be a balanced bipartite graph of order 2n. If ||G|| ≥ n 2n + 3, then G is hamiltonian biconnected and 2-hamiltonian biconnected.

Proof: The proof will be divided into two steps. We first show that Theorem 5 is true for m = n. In the second step we will consider the situation when m < n.

Step 1. m = n

We will proceed by induction on k.

We assume, without loss of generality, that the size of G is equal to f (n, n, k), for otherwise we may consider a spanning subgraph of G with exactly f (n, n, k) edges instead of G.

Let k = 0. We want to show that if G is a balanced bipartite graph with |G| = 2n ≥ 8 and ||G|| = n 2 -n + 1 then G is bipancyclic unless G ∈ G n,n,0 .
Applying Theorem 6 to the graph G, we get that either G is bipancyclic, or else there are two nonadjacent vertices x ∈ X and y 2 , so G -{x, y} is a complete balanced bipartite graph on 2n -2 vertices (hence G contains cycles of all even lengths up to 2n -2). If so, then, in fact, d G (x) + d G (y) = n. Since x and y are not adjacent, their degrees are both greater than zero. In case d G (x) ≥ 2 and d G (y) ≥ 2 it is easy to find a hamiltonian cycle in G. It remains to consider the case when one of the vertices x and y, say x, has degree 1. Then y has degree n -1 and is adjacent to every vertex of the set X \ {x}, which implies G ∈ G n,n,0 . Now assume the theorem holds for k -1, k ≥ 1; we will prove that it holds also for k.

∈ Y such that d G (x)+d G (y) ≤ n. But then ||G-{x, y}|| ≥ n 2 -n + 1 -n = (n -1)

Let us start with the observation that

f (n, n, k) -f (n -1, n -1, k -1) = n -k.
In the proof we shall consider two cases.

C 2n-2k ⊂ G or G ∈ G n,n,k . It is easy to check that C 2n-2k ⊂ G in case d G (x) ≥ 2. It remains to consider what happens when d G (x) ≤ 1. Suppose that d G (x) = 0. Then d G (y) = n -k > k,
which implies that there is at least one vertex in the set A, say v 1 , and at least one vertex, say v 2 , in the set B which are adjacent to the vertex y. In this case it is a simple matter to find a cycle C 2n-2k contained in G which passes through the vertices v 1 , y and v 2 . So suppose that d G (x) = 1, which implies d G (y) = nk -1 > k. Then either the vertex y is adjacent to all vertices in the set A (which means that G ∈ G n,n,k ), or, again, y is adjacent to some vertex of A and to at least one vertex in B, and we again find a cycle of length 2n -2k contained in G.

Case 2. Suppose for every pair of vertices x ∈ X and y ∈ Y in the graph G, we have

d G (x) + d G (y) ≥ n -k + 1.
Firstly, observe that this assumption implies that δ(G) ≥ 2, for otherwise G has at least n(nk) edges, which contradicts the assumption made at the beginning of Step 1 that ||G|| = f (n, n, k).

x is joined only with at most k vertices of V ′ , which is a consequence of the construction of G k+1 ), so, by the assumption made at the beginning of Case 2,

d G (u) ≥ n -2k + 1 for every vertex u ∈ Y ∩ V ′ . For n ≥ 1 2 k 2 + 3 2 k + 4, it follows that d G (u) ≥ k + 2, which leads to e(u, V (G k+1 )) ≥ 2, since u ∈ Y ∩ V ′ has at least one non-neighbour in X ∩ V ′ .
Since δ(G) ≥ 2, the vertex x has at least two neighbors in V ′ , say y, y ′ . By the above observation, there are two different vertices

v 1 , v 2 ∈ X ∩ V (G k+1 ) such that v 1 y ∈ E and v 2 y ′ ∈ E. G k+1 is hamiltonian, so there exists a vertex u ∈ Y ∩ V (G k+1 ) such that v 1 u ∈ E. Let a ∈ Y ∩ V (G k+1 ) and a = u. Since G k+1 is 2-hamiltonian biconnected, G k+1 -{v 1 ,
a} is hamiltonian biconnected, so there exists a v 2 u-path of order 2n -2k -4 in G k+1 -{v 1 , a}. We can extend this path to a cycle of length 2n -2k using edges v 2 y ′ , y ′ x, xy, yv 1 , v 1 u, a contradiction with the assumption that C 2n-2k ⊂ G.

Step 2. m < n First order the vertices of Y = {y 1 , ..., y n } so that d G (y 1 ) ≤ . . . ≤ d G (y n ). Put Y ′ := {y 1 , ..., y n-m }. We shall consider two cases depending on the degree of the vertex y n-m .

Case 1. d G (y n-m ) ≥ m -k Then G -Y ′ is a balanced bipartite graph on 2m vertices such that ||G -Y ′ || ≥ m(m -k) > f (m, m, k) since m > k + 1. From what has already been proved in Step 1, we conclude that G -Y ′ ⊃ C 2p for all 2 ≤ p ≤ m -k, which completes the proof in this case. Case 2. d G (y n-m ) ≤ m -k -1 Now we have ||G -Y ′ || ≥ f (m, n, k) -(n -m)(m -k -1) = f (m, m, k) (1)
which again implies G -Y ′ ⊃ C 2p for all 2 ≤ p ≤ m -k -1, and also G -Y ′ ⊃ C 2m-2k unless ||G -Y ′ || = f (m, m, k) and G -Y ′ ∈ G m,m,k .
Therefore it remains to consider the situation when

X = A ∪ B, where A = {v : d G-Y ′ (v) = m}, B = {v : d G-Y ′ (v) = 1}, |B| = k + 1.
Then every vertex of Y ′ has degree in G equal mk -1 since inequality 1 is, in fact, an equality. Suppose now that no cycle of length 2m -2k is contained in G. Consequently, no vertex of Y ′ can be adjacent to both a vertex of A and a vertex of B, for otherwise we could simply construct a cycle C 2m-2k in G. Hence the assumption: d G (y i ) = mk -1 for all 1 ≤ i ≤ nm, implies (for m > 2k + 2) that every vertex of Y ′ is adjacent to all vertices of A. It follows that G ∈ G m,n,k , which completes the proof.

✷ 3 Conjecture

We expect that the condition on the order of G in Theorem 5 may be relaxed. We formulate the following conjecture. Notice that the assumption m ≥ 2k + 2 of the conjecture is weakest possible, as shown by the following example.

Example 1 Let G 1 = (X, Y ; E) be a bipartite graph with vertex classes of the form There are some results which suggest that this conjecture may be true.

X = Q ∪ R, Y = S ∪ T , where |Q| = |T | = m -k -1, |R| = k + 1, |S| = n -m + k + 1, m ≤ n.
It is true for k = 0 (Theorem 4). We will show that it is true also for k = 1 but we will need the following result (stronger than Theorem 3).

Theorem 8 Let G = (X, Y ; E) be a balanced bipartite graph of order 2n.

If ||G|| ≥ n 2 -n + 1, then G is bipancyclic or G ∈ G n,n,0 .
The proof of Theorem 8 is the same as that of Theorem 5 in the case k = 0 in Step 1. Now we are ready to prove Conjecture 1 for k = 1.

Sketch of proof of Conjecture 1: An analysis similar to that in Step 2 of the proof of Theorem 5 shows that Conjecture 1 is true in general case (m ≤ n) if it is true for balanced bipartite graphs (m = n). Therefore it remains only to consider the situation when m = n. Suppose that there exists 2 ≤ p ≤ n -1 such that G does not contain any cycle of length 2p. Then, by Theorem 6, there are two nonadjacent vertices x ∈ X and y ∈ Y such that d In 1985, Jackson [START_REF] Jackson | Long cycles in bipartite graphs[END_REF] found the number of edges of a bipartite graph G needed to ensure the existence of a cycle of length at least 2p in G. Conjecture 1, if true, would be a significant strengthening of the following theorem. There is another result which suggest that Conjecture 1 may be true. Gyárfás, Rousseau and Schelp solved an analogous problem for paths in bipartite graphs. They characterized all extremal graphs for this problem, which are similar to those of the family G m,n,k .

G (x) + d G (y) ≤ n. Hence ||G -{x, y}|| ≥ n 2 -2n + 3 -n = (n -1) 2 -(n -1) + 1. By Theorem 8, G -{x, y} ∈ G n-1,n-1,

Fig. 1 :

 1 Fig. 1: The family G m,n,k of extremal graphs.

Case 1 .

 1 Suppose there are two vertices x ∈ X and y ∈ Y in the graphG such that d G (x) + d G (y) ≤ nk.Then G -{x, y} is a balanced bipartite graph with 2n -2 vertices and at least f (n, n, k)-(nk) = f (n -1, n -1, k -1)edges. By the inductive hypothesis there are cycles of all even lengths up to 2(n -1) -2(k -1) = 2n -2k contained in G -{x, y}, hence also in G, unless G -{x, y} ∈ G n-1,n-1,k-1 . In the latter case d G (x) + d G (y) = nk and x and y are not adjacent, because ||G -{x, y}|| = f (n -1, n -1, k -1). Moreover, X \ {x} = A ∪ B, where A = {v : d G-{x,y} (v) = n -1}, B = {v : d G-{x,y} (v) = 1} and |B| = k. We see at once that cycles of all even lengths up to 2n -2k -2 are contained in G -{x, y}, hence also in G. What remains to show is that either

Conjecture 1

 1 Let G = (X, Y ; E) be a bipartite graph with |X| = m ≤ n = |Y |, where m ≥ 2k + 2, k ∈ N. If ||G|| > n(mk -1) + k + 1,then G contains cycles of all even lengths up to 2m -2k.

  Fix a vertex y 0 in T , and let N G1 (v) = S ∪ {y 0 } for all v ∈ Q, and N G1 (w) = T for all w ∈ R. ThenG 1 > n(mk -1) + k + 1 for k + 3 ≤ m ≤ 2k + 1, yet G 1 contains no cycle of length greater than 2m -2k -2.Hence the necessity of the assumption m ≥ 2k + 2.

  0 , and therefore contains cycles of all even lengths up to 2n-4. Since ||G-{x, y}|| = n 2 -3n+3, we must have d G (x) + d G (y) = n. But the assumption C 2n-2 ⊂ G implies that d G (x) ≤ 1 and d G (y) ≤ n -2, a contradiction. ✷

Theorem 9 (

 9 Jackson [6])Let G = (X, Y ; E) be a bipartite graph with |X| = m ≤ n = |Y |, where m ≥ 2k + 2, k ∈ N. If ||G|| ≥ n(mk -1) + k + 2, then there exists p ≥ mk such that C 2p ⊂ G.

Theorem 10 (

 10 Gyárfás, Rousseau and Schelp[START_REF] Gyárfás | An extremal problem for paths in bipartite graphs[END_REF])Let G = (X, Y ; E) be a bipartite graph with |X| = m ≤ n = |Y |, where m > 2k + 2, k ∈ N. If ||G|| ≥ n(mk -1), then either P 2m-2k ⊂ G or ||G|| = n(mk -1) and G is the exceptional graph for which X = A ∪ B, A = {x ∈ X : d G (x) = n}, B = {x ∈ X : d G (x) = 0}, |B| = k + 1.

Acknowledgements

The author wishes to express his thanks to Irmina Zioło, Paweł Wojda and Jakub Przybyło for their helpful and valuable remarks.

† The research was partially supported by the AGH University of Science and Technology grant No. 11.420.04 and by the Polish Ministry of Science doctoral grant No. 0102/M03/2007/32. 1365-8050

Suppose now that there exists 2 ≤ p ≤ nk such that G does not contain any cycle of length 2p. Theorem 6 implies that there are two nonadjacent vertices x 1 ∈ X and y 1 ∈ Y such that d G (x 1 ) + d G (y 1 ) ≤ n. Let G 1 := G -{x 1 , y 1 }. Observe that ||G 1 || ≥ f (n, n, k)n. Now, we apply Theorem 6 to the graph G 1 . Since there exists some p ∈ {2, . . . , n -k} such that C 2p ⊂ G, the subgraph G 1 of G does not contain C 2p and, in particular, G 1 is not bipancyclic. Thus, there are two nonadjacent vertices

We now apply Theorem 6 to the graph G 2 , and so on. After k + 1 steps we finally get the graph

and G k+1 is hamiltonian biconnected and 2-hamiltonian biconnected by Theorem 7, and also bipancyclic by Theorem 3. It follows that there are cycles of all even lengths up to 2n -2k -2 contained in G k+1 , hence also in G. So the hypothesis, that there exists

). We need to consider several subcases.

Subcase 2.1. Assume there are two vertices

and there is a vertex v ∈ X ∩ V (G k+1 ) which is adjacent to y. There exists a uv-path of order 2n -2k -2 in G k+1 , because G k+1 is hamiltonian biconnected. It means that there is a path P 2n-2k = x 1 y 1 x 2 y 2 . . . x 2n-2k y 2n-2k (x 1 = x, y 1 = u, x 2n-2k = v, y 2n-2k = y) contained in G, which passes through all vertices of the graph G k+1 . Since C 2n-2k ⊂ G, if x 1 y i ∈ E then x i y 2n-2k ∈ E, for otherwise x 1 y 1 x 2 y 2 . . . x i y 2n-2k x 2n-2k . . . y i x 1 is a cycle of length 2n -2k contained in G. Thus, we have e(x, V (G k+1 )) + e(y, V (G k+1 )) ≤ nk, which, in this case, means that d G (x) + d G (y) ≤ nk, contradicting the assumption.

Subcase 2.2. Assume for every pair of vertices x ∈ X ∩ V ′ and y ∈ Y ∩ V ′ , we have e(x, V ′ ) = 0 or e(y, V ′ ) = 0.

We then consider an edge xy with x ∈ X ∩ V ′ , y ∈ Y ∩ V ′ .

Subcase 2.2.1. Suppose for at least one edge xy with x ∈ X ∩ V ′ , y ∈ Y ∩ V ′ , we have e(x, V (G k+1 )) ≥ 1 and e(y, V (G k+1 )) ≥ 1.

Then, again, there is a vertex u ∈ Y ∩ V (G k+1 ) which is adjacent to x, and there is a vertex v ∈ X ∩ V (G k+1 ) which is adjacent to y, and there exists a uv-path of order 2n -2k -2 in G k+1 . We can extend this path to a cycle of length 2n -2k using edges ux, xy, yv, a contradiction with the assumption that C 2n-2k ⊂ G.

Subcase 2.2.2. Suppose for every edge xy with x ∈ X ∩ V ′ , y ∈ Y ∩ V ′ , we have e(x, V (G k+1 )) = 0 or e(y, V (G k+1 )) = 0.

Without loss of generality we may assume that e(x, V (G k+1 )) = 0. We show that e(u, V (G k+1 )) ≥ 2 for every vertex u ∈ Y ∩ V ′ . We have d G (x) ≤ k (because


Gábor Bacsó

Zsolt Tuza

Clique-transversal sets and weak 2-colorings in graphs of small maximum degree †

Keywords: 2000 Mathematics Subject Classification: 05C15, 05C69, 05C85 clique-transversal set, weak coloring, clique coloring, cubic graph, claw-free graph, polynomial-time algorithm

A clique-transversal set in a graph is a subset of the vertices that meets all maximal complete subgraphs on at least two vertices. We prove that every connected graph of order n and maximum degree three has a clique-transversal set of size ⌊19n/30 + 2/15⌋. This bound is tight, since 19n/30 -1/15 is a lower bound for infinitely many values of n. We also prove that the vertex set of any connected claw-free graph of maximum degree at most four, other than an odd cycle longer than three, can be partitioned into two clique-transversal sets. The proofs of both results yield polynomial-time algorithms that find corresponding solutions.

Introduction

We consider finite, simple undirected graphs G = (V, E), with vertex set V and edge set E. The number of vertices will be denoted by n.

There are slight differences in the usage of the term 'clique' in graph theory. Throughout this paper, we use clique with the following restricted meaning: inclusion-wise maximal complete subgraph with at least two vertices. Hence, isolated vertices will not be called cliques, and maximality under inclusion will be required.

A clique-transversal set is a set S ⊆ V that meets all cliques of G. The smallest cardinality of a cliquetransversal set in G, called clique-transversal number, is denoted by τ C (G). A weak 2-coloring of G is a mapping φ : V → {r, g} (say red, green) such that both φ -1 (r) and φ -1 (g) are clique-transversal sets. If such φ exists, we say that G is weakly 2-colorable.

This notion can be extended to weak k-coloring, also called k-clique-coloring in the literature, which assigns one of k colors to each vertex in such a way that no clique is monochromatic. Equivalently, graph G is weakly k-colorable if there exists a partition V 1 ∪ • • • ∪ V k = V such that no V i contains any cliques of G. The smallest nonnegative integer k admitting a weak k-coloring will be denoted by χ C (G).

Gábor Bacsó and Zsolt Tuza

1.1 Some standard terminology For d = 3, 4 we denote by G d the class of connected graphs of maximum degree at most d. The members of G 3 are the connected subcubic graphs, and those 3-regular ones are called cubic. The degree of vertex v will be denoted by d(v). A vertex is simplicial if its neighbors are mutually adjacent.

Given a "forbidden" graph F , graph G is called F -free if no induced subgraph of G is isomorphic to F . In the cases of F = K 3 , F = K 1,3 , and F = K 4 -e (one edge removed from K 4 ), we use the standard terms triangle-free, claw-free, and diamond-free, respectively. A hole is a chordless cycle of length at least four.

Results and history

The graph invariant τ C was introduced by Gallai [13] and then studied by various authors. The earliest published results deal with chordal graphs [START_REF] Zs | Covering all cliques of a graph[END_REF], relating τ C with the number of vertices under the assumption that each edge is contained in some clique of given order. The case of τ C ≤ n/2 has been analyzed for line graphs and their complements [START_REF] Th | Clique-transversal sets of line graphs and complements of line graphs[END_REF], and some general bounds on τ C appeared in [START_REF] Erdős | Covering the cliques of a graph with vertices[END_REF].

It should be noted that if G is triangle-free, then a set is a clique-transversal set of G if and only if it meets all edges-i.e., it is a vertex cover-therefore τ C (G) is equal to the number of vertices minus the independence number of G in this case. This also means that the determination of τ C is algorithmically hard, on many restricted classes of graphs. Structured hard classes with respect to τ C can be found in [START_REF] Chang | Algorithmic aspects of neighbourhood numbers[END_REF][START_REF] Guruswami | Algorithmic aspects of clique-transversal and cliqueindependent sets[END_REF][START_REF] Chang | Algorithmic aspects of the generalized cliquetransversal problem on chordal graphs[END_REF], whereas polynomial-time algorithms for other classes are given in [START_REF] Balachandhran | Clique transversal and clique independence on comparability graphs[END_REF][START_REF] Chang | Algorithmic aspects of neighbourhood numbers[END_REF][START_REF] Lee | Distance-hereditary graphs are clique-perfect[END_REF].

Liang et al. [START_REF] Liang | Clique-transversal sets in cubic graphs[END_REF] proved the following estimates on the clique-transversal number.

1. Every connected cubic graph G of order n > 4 has 5n/14 ≤ τ C (G) ≤ 2n/3.

2.

There exist infinitely many cubic connected graphs with τ C (G) = 3n/5.

The estimates of 1 were proved also in [START_REF] Shan | Bounds on the clique-transversal number of regular graphs[END_REF], and the graphs attaining the lower bound were characterized in both papers. Determining χ C (G) is hard: to decide χ C = 2 is NP-complete on 3-chromatic perfect graphs [START_REF] Kratochvíl | On the complexity of bicoloring clique hypergraphs of graphs[END_REF], and can be even harder: it is Σ p 2 -complete on unrestricted input graphs [START_REF] Marx | Complexity of clique coloring and related problems[END_REF]. On the positive side, all planar graphs have χ C ≤ 3 [START_REF] Mohar | The Grötzsch theorem for the hypergraph of maximal cliques[END_REF] and χ C = 2 can be tested in polynomial time if the input is restricted to planar instances [START_REF] Kratochvíl | On the complexity of bicoloring clique hypergraphs of graphs[END_REF], hence χ C on planar graphs can be determined efficiently.

A necessary and sufficient condition for χ C ≤ k on line graphs was given in [START_REF] Th | Clique-transversal sets of line graphs and complements of line graphs[END_REF]. Moreover, claw-free perfect graphs are weakly 2-colorable [START_REF] Bacsó | Coloring the maximal cliques of graphs[END_REF]. It was erroneously stated in [17, page 114] that the upper bound τ C ≤ n/2 implies χ C ≤ 2 for claw-free cubic graphs; later, however, in an unpublished manuscript the authors of [START_REF] Liang | Clique-transversal sets in cubic graphs[END_REF] gave a proof for weak 2-colorability. Here we extend this latter result by dropping the condition of regularity and also weakening the condition on vertex degrees.

Theorem 2 Every connected claw-free graph of maximum degree at most four, other than an odd hole, is weakly 2-colorable. Moreover, a weak 2-coloring can be found in polynomial time.

These results are proved in Sections 2 and 3, respectively. Some related problems are mentioned in the concluding section.

Transversal sets

In this section we prove Theorem 1. Let us begin with the proof of tightness, and then proceed with the upper bounds.

Proof of Parts 3 and 4. Locke [START_REF] Locke | Bipartite density and the independence ratio[END_REF] constructed an infinite family of connected cubic triangle-free graphs with n := 30k + 22 vertices and independence number 11k + 8. Thus, in every such graph G we have Proof of Parts 1 and 2. Let G = (V, E) be a subcubic connected graph of order n. Suppose first that G is triangle-free. If G is not 3-regular, we first run the O(n 4 ) algorithm of Fraughnaugh and Locke [START_REF] Fraughnaugh | 11/30 (Finding large independent sets in connected triangle-free 3-regular graphs)[END_REF], which finds an independent set W of size at least 11n/30 -1/30 in G. Then the set

τ C (G) = 19k + 14 = 19(n -22)/30 + 14 = 19n/30 -1/15.
S := V \ W, |S| ≤ 19n/30 + 1/30
meets all edges of G and hence is a clique-transversal set of required size, found in polynomial time. If G is triangle-free and cubic, then the algorithm in [START_REF] Fraughnaugh | 11/30 (Finding large independent sets in connected triangle-free 3-regular graphs)[END_REF] guarantees a slightly weaker lower bound |W | ≥ 11n/30 -2/15 on the size of independent set W , and we obtain |S| ≤ 19n/30 + 2/15 in this case.

Suppose from now on that G contains a triangle, say T with vertex set

{x 1 , x 2 , x 3 }. Each x i ∈ T (i = 1, 2, 3) has at most one neighbor outside T . We assume d(x 1 ) ≥ d(x 2 ) ≥ d(x 3 ), and if d(x i ) = 3 then denote the neighbor of x i outside T by y i . If d(x 1 ) = 2, then G ≃ K 3 ; and if d(x 3 ) = 3 and y 1 = y 2 = y 3 , then G ≃ K 4 .
In either case, τ C (G) = 1 ≤ n/3 holds, and we have nothing to prove. Similarly, it is easy to check that τ C (G) ≤ n/2 is valid if n ≤ 4. Hence, we assume d(x 1 ) = 3 and n > 4.

We shall apply induction on n, assuming that the upper bound τ C (G ′ ) ≤ 19n ′ /30 + 1/30 is valid for all non-cubic G ′ ∈ G 3 of order n ′ < n. For disconnected subcubic graphs with K components, none of which is cubic, this equivalently means τ C (G ′ ) ≤ 19n ′ /30 + K/30. Note that no proper subgraph of G can have cubic components, because G is connected. The following simple fact will also be useful. Time analysis. Let us choose a polynomial P (x) satisfying the following properties: P (x) is monotone increasing for x > 0, P (n) is an upper bound for all n on the running time of the O(n 4 ) algorithm in [START_REF] Fraughnaugh | 11/30 (Finding large independent sets in connected triangle-free 3-regular graphs)[END_REF] for triangle-free subcubic graphs, moreover

P (x ′ ) + P (x ′′ ) ≤ P (x ′ + x ′′ ) and P (x -3) + cx ≤ P (x)
for all x ′ , x ′′ ≥ 1, all x ≥ 4, and for some constant c to be fixed later. For instance, if 4 i=0 a i x i is a valid bound for [START_REF] Fraughnaugh | 11/30 (Finding large independent sets in connected triangle-free 3-regular graphs)[END_REF], then P (x) := 4 i=0 |a i |x i + cx 2 will do; and any faster algorithm for triangle-free graphs would yield a stronger estimate for the general case, too.

If G is triangle-free, then the algorithm terminates in at most P (n) steps by assumption. Otherwise, triangle T can be found in c 1 n steps for some constant c 1 , e.g. applying breadth-first search and checking at each vertex whether its two descendants (or possibly three for the root vertex) are adjacent or not.

The removal of 3, 4, or 5 vertices takes constant time. Assuming that the remaining graph has connected components of orders n 1 , . . . , n k , we need at most c 2 (n 1 + . . . + n k ) steps to determine its components and at most P (n 1 ) + . . . + P (n k ) ≤ P (n 1 + . . . + n k ) ≤ P (n -3) steps to find the partial cliquetransversal set S ′ . In this way, choosing c = c 1 + c 2 we obtain that P (n) is an upper bound on the total running time. ✷

Weak 2-coloring

In this section we prove Theorem 2. Since even cycles are trivial to 2-color, we assume that G is not a cycle. It will turn out that diamond-free graphs admit a more elegant approach than general ones, therefore we treat them first; and afterwards the idea will be to identify a diamond D, find a weak 2-coloring of G -D, and prove that it can be extended to a weak 2-coloring of G. So, assume first that G is connected, claw-free and also diamond-free, has maximum degree at most four, and is not a chordless cycle of length greater than three. Under these conditions we say that G is a safe graph. Moreover, Let us call a vertex x safe if it satisfies the following requirements:

1. G -x is connected, 2. G -x is not a cycle longer than three, 3.
x is either a pendant vertex or contained in a K 3 ⊆ G.

For a safe vertex x we define its critical neighbor y-whose choice is not always unique-as follows.

• If d(x) = 1, then y is the unique neighbor of x.

• If x is in some triangle T x , let K x be the (unique) clique containing T x .

-If x has neighbor(s) outside K x , let y / ∈ K x be any such neighbor. -Otherwise, let y ∈ K x be any neighbor of x.

Note that K x is well-defined because each edge (and hence also each triangle) of G lies in a unique clique, otherwise G would not be diamond-free. For the same reason, x cannot occur in two triangle cliques which share a further vertex. And x cannot be involved in two cliques of size two either, because they would induce a claw with a vertex of T x . On the other hand, it can happen that x is incident with two edge-disjoint triangles, in this case T x = K x can be chosen as any one of them.

We proceed with some properties concerning safe vertices in safe graphs.

Lemma 1 If x is a safe vertex in a safe graph G, and x is contained in a triangle T x , then also K x -x is a clique in G -x for the unique clique K x containing T x in G.

Proof: Otherwise, there is a vertex z adjacent to all vertices of K x . In this case, xy must be a non-edge, by the maximality of K x . But then T x ∪ {z} induces a diamond, a contradiction. ✷ Lemma 2 Every safe graph of order greater than one has a safe vertex.

Proof: Let G be a safe graph. Suppose first that G has a leaf x. The only safe-vertex-defining condition which could be violated is 2, but then we would find a claw in G. Thus, x is safe. Assume next that G has no pendant vertices. Then G is not a tree, and it contains a chordless cycle. If this cycle can be chosen with length at least four, then we denote it by C. Since G is not a cycle, there exists some vertex u adjacent to C. Claw-freeness implies that there is an edge e = xy in C such that xyu is a triangle. If G -x is disconnected, then the two neighbors of x on C and a third neighbor in another component of G -x form a claw with center x. Hence, G -x has to be connected, and again it suffices to check whether Condition 2 is valid.

Suppose on the contrary that the graph G -x is a chordless cycle. Let z = y be the other neighbor of x on C. In this case, G -x consists of two paths, namely P := C -x from y to z and a z-u path Q, completed to a chordless cycle with edge uy. The neighbors of x are y, u, z, and the neighbor of z on Q. This is the only situation where x violates Condition 2. But then both y and z are safe in G.

Finally, if G has no chordless cycles of length at least four, then G is chordal, by definition. It is a well-known fact that a chordal graph has a simplicial vertex x, which clearly is safe. ✷ Lemma 3 Let x be a safe vertex in a safe graph G = (V, E), with critical neighbor y. If φ : V \ {x} → {r, g} is a weak 2-coloring of G -x, then φ(x) := {r, g} \ {φ(y)} extends it to a weak 2-coloring of G.

Proof: Suppose on the contrary that some monochromatic clique R occurs in G, say completely red. Of course, x ∈ R and |R| ≥ 2. Let W be the complete subgraph R -x. This W is not maximal in G -x since φ is a weak 2-coloring of G -x. Hence, By Lemma 1 we have |W | = 1, say W = {w}. Note that w = y because φ(w) = φ(x) = φ(y). Vertex x is not pendant, therefore its K x is well-defined. Since the edge wx is a clique in G and so it cannot be contained in any triangle, we see that wy / ∈ E, moreover w is not in K x -x. By Lemma 1, K x -x is a clique in G -x, consequently both y and w have some non-neighbors in K x -x; denote one non-neighbor by y ′ and w ′ , respectively. Then yw ′ is an edge, otherwise {x, y, w, w ′ } would induce a claw. But now yy ′ / ∈ E implies y ′ = w ′ and that {x, y, y ′ , w ′ } induces a diamond, a contradiction. ✷

Based on these lemmas, we design Algorithm 1 as a subroutine for the general algorithm to find a weak 2-coloring.

Algorithm 1 SAFECOL(G) -Weak 2-coloring of safe graphs Require: Safe graph G = (V, E). Ensure: Weak 2-coloring φ : V → {r, g}. 1: if |V | = 1 then {assume V = {v}} 2:
φ(v) := g 3: else 4: Find safe vertex x and its critical neighbor y 5: SAFECOL(G -x) 6: φ(x) := {r, g} \ {φ(y)} Time analysis for Algorithm 1. Apart from the recursive call in Step 5, the only time-consuming instruction is to identify a safe vertex in Step 4. Efficient implementation is ensured by the following claim.

Lemma 4 A safe vertex in a safe graph can be found in linear time.

Proof: The non-cutting vertices x of G can be enumerated in O(n) steps, and since G has bounded maximum degree (and also because it is claw-free), for each x it can be tested in constant time whether or not x is incident with a triangle. Finally, G -x can be a cycle for at most one choice of x. ✷

Hence, storing the eliminated vertices in a stack, the recursive call of Step 5 (which yields iterated executions of Steps 4 and 6) can be implemented efficiently. As a consequence, Algorithm 1 requires not more than O(n 2 ) steps.

The following side-product of our method appears to be of interest on its own right, too.

Remark 2 Since every subgraph of any safe G ≃ K 1 contains a safe vertex, a "safe elimination order" can be determined.

From now on we suppose that G contains a diamond D ≃ K 4 -e. Some cliques of G have vertices in both D and G -D; we call them crossing cliques. If a crossing clique Q has just one vertex in D, we say that Q is a strong crossing clique; and otherwise we say that Q is weak.

As for notation, we assume that the diamond D found in G has vertex set {c 1 , c 2 , d 1 , d 2 }, where the only non-edge is {c 1 , c 2 }. By the degree assumption, there can occur at most one edge from d i to M := G-D, and at most two edges from c i to M (i = 1, 2). Due to these degree constraints and the assumption that G is claw-free, combinations of the following crossing cliques may occur:

• strong edge: c i a i (at most one for each i ∈ {1, 2})

• strong triangle: c i b ′ i b ′′ i (at most one for each i ∈ {1, 2}) • weak triangle: c i d j w i,j (at most one for each pair (i, j))

• weak 4-clique: c i d 1 d 2 z i (at most one for each i ∈ {1, 2}) Degree bounds on d 1 , d 2 imply that if both w 1,j , w 2,j exist, then w 1,j = w 2,j ; and similarly, if both z 1 , z 2 exist, then z 1 = z 2 . Moreover, weak triangles of type d 1 d 2 v would create a claw, hence are excluded.

The procedure can now be formalized as described in Algorithm 2. The heart of the proof is expressed in the following assertion.

Algorithm 2 CLQCOL(G) -Determination of weak 2-coloring Require: Claw-free connected graph G = (V, E) of maximum degree at most 4, not a hole. Ensure: Weak 2-coloring φ : V → {r, g}.

1: if G is diamond-free then {G is safe} else {assume H ≃ C ℓ , ℓ ≥ 4, vertices labeled x 1 , . . . , x ℓ sequentially along H} 9:

if ℓ is even then 10:

φ(x i ) := g for i odd (i = 1, 3, . . . , ℓ -1), φ(x i ) := r for i even (i = 2, 4, . . . , ℓ)

11:

if ℓ is odd then Proof: Suppose that a weak 2-coloring φ of G -D has been fixed. We wish to extend it to the entire G without changing any color in G -D; the extension will also be denoted by φ.

Once we decide that φ(d 1 ) = φ(d 2 ) holds, all cliques of G with three vertices in D are 2-colored. This includes the triangles of D and the weak 4-cliques, too, if there are any. Therefore, we only have to show that the crossing cliques of orders two and three-strong edge, strong triangle, weak triangle-are 2-colorable under this condition.

A strong crossing clique may determine the color of c i . Namely, φ(c i ) = {r, g} \ {φ(a i )} must hold in a strong edge, and likewise, φ(b

′ i ) = φ(b ′′ i ) in a strong triangle forces φ(c i ) = {r, g} \ {φ(b ′ i )}.
Since each c i is incident with at most one strong clique, two contradictory conditions of this kind cannot occur at c i . Moreover, apart from these situations, we have no a priori restriction on the colors of c 1 and c 2 .

Concluding remarks

Here we put a couple of simple observations and mention some problems, which would be of interest for future research. NP-completeness. From the well-known fact that the independence number is NP-complete to determine on cubic graphs, in connection with Theorem 1 we can derive that the complexity of finding τ C is NP-complete on triangle-free cubic graphs. The proof can be done in two steps:

• Given a cubic graph G = (V, E), replace each edge e = xy ∈ E by a path xv e w e y of length three.

This operation yields a subcubic triangle-free graph H, and increases the independence number by exactly |E|.

• Take two copies H ′ , H ′′ of H and insert the edges v ′ e w ′′ e and v ′′ e w ′ e for all e ∈ E. This results in a cubic triangle-free graph whose independence number is the double of that in H.

Optimum running time. Although our algorithms run in polynomial time, we expect that the orders of those polynomials are not optimal. For this reason, it is natural to ask: Problem 1 Determine the best asymptotic running time of an algorithm for 1. finding clique-transversal sets of size at most 19n/30 + O(1) in connected subcubic graphs, 2. finding weak 2-colorings in claw-free graphs of maximum degree four.

Clique-transversal number vs. clique size. The flavor of results in [START_REF] Zs | Covering all cliques of a graph[END_REF] is that if every edge of a 'nicely structured' graph lies in a 'large' clique, then τ C is 'small'. This direction has been pursued in [START_REF] Th | On covering all cliques of a chordal graph[END_REF] and recently in [START_REF] Aparna Lakshmanan | The t -property of some classes of graphs[END_REF]. We think that there are many further classes of graphs for which such kind of results would be of interest to study.

Line graphs. The line graph of K 6 is 8-regular and is not weakly 2-colorable. This fact, together with our Theorem 2, leads to the following problem.

Problem 2 Find the largest integer d such that every claw-free graph of maximum degree d is weakly 2-colorable.

Perfect graphs. A long-standing open problem of Duffus et al. [START_REF] Duffus | Two-coloring all two-element maximal antichains[END_REF] asks whether χ C is bounded above by a constant on the class of perfect graphs. In fact, no examples of perfect graphs G with χ C (G) > 3 are known. The upper bound χ C ≤ 3 has been proved for some classes of perfect graphs in [START_REF] Bacsó | Coloring the maximal cliques of graphs[END_REF]. Moreover, it is immediate by definition that every strongly perfect graph is weakly 2-colorable.

  If a non-regular connected graph is needed, we omit just one non-cutting vertex. Denoting n := 30k + 21 we obtain τ C (G) = 19k + 13 = 19(n -21)/30 + 13 = 19n/30 -3/10.

Remark 1

 1 Removing any set U of vertices, the number of components in the remaining graph cannot be larger than the edges connecting U with V \ U .Wenow proceed with the inductive step for the upper bound on τ C . If d(x 2 ) = 2, then G -T is connected and it has a clique-transversal set S ′ of size at most 19(n -3)/30 + 1/30 by the induction hypothesis. Since S := S ′ ∪ {x 1 } is a clique-transversal set in G, the upper bound τ C (G) ≤ 19n/30 -13/15 follows. Suppose d(x 2 ) = 3 and y 1 = y 2 . If d(x 3 ) = 2, or d(x 3 ) = 3 but y 3 = y 1 (or y 3 = y 2 ), we consider the graph G -T -y 1 (or G -T -y 2 ). Since it has at most three connected components by Remark 1, it contains a clique-transversal set S ′ of size at most 19(n -4)/30 + 3/30, and then S := S ′ ∪ {y 1 , x 2 } meets all cliques of G. Thus, τ C (G) ≤ 19n/30 + (3 -76 + 60)/30 = 19n/30 -13/30. Finally, suppose d(x 3 ) = 3 and y 1 = y 2 = y 3 = y 1 . We now consider G -T -y 1 -y 2 . By Remark 1 it has at most five connected components. Hence, by the induction hypothesis, it has a clique-transversal set S ′ of size at most 19(n -5)/30 + 5/30, and S := S ′ ∪ {y 1 , y 2 , x 3 } is a clique-transversal set in G. Thus, τ C (G) ≤ 19n/30 + (5 -95 + 90)/30 = 19n/30.

12 :

 12 Find edge e ∈ E(H) contained in a crossing clique Q {assume e = x 1 x ℓ } 13: φ(x i ) := g for i odd (i = 1, 3, . . . , ℓ), φ(x i ) := r for i even (i = 2, 4, . . . , ℓ -1) 14: Find φ : {c 1 , c 2 , d 1 , d 2 } → {r, g} with φ(d 1 ) = φ(d 2 ), s.t. no monochromatic crossing clique occurs {such φ exists; see text} Lemma 5 Let G ∈ G 4 be claw-free, and D a diamond in G. If no component of G -D is an odd hole, then every weak 2-coloring of G -D can be extended to a weak 2-coloring of G in such a way that the two vertices of degree three inside D get distinct colors.

  Find diamond D, label its vertices c 1 , c 2 , d 1 , d 2 such that c 1 c 2 / ∈ E 5: for all components H of G -D do

	2:	SAFECOL(G)
	3: else
	4: 6:	if H not a cycle longer than 3 then
	7:	CLQCOL(H)
	8:

† Research supported by the Hungarian Scientific Research Fund, grant OTKA T-049613. 1365-8050

Suppose first that c 1 a 1 is a strong edge. Then c 1 cannot be incident with any crossing triangles: a strong one is impossible by the degree condition, and a weak triangle c 1 d 1 w 1,1 would create a claw on {c 1 , d 2 , a 1 , w 1,1 } because c 1 a 1 is a clique and hence a 1 cannot be adjacent to any neighbor of c 1 . Consequently, φ(c 1 ) := {r, g} \ {φ(a 1 )} yields a 2-coloring for all crossing cliques incident with c 1 . The same argument applies if there is a strong edge c 2 a 2 .

The situation is similar and only slightly more complicated if there is a strong triangle, say From now on we may assume that c 1 and c 2 are contained in weak triangles only. We select one c 1 d i w 1,i and one c 2 d j w 2,j , and define φ(c 1 ) := {r, g} \ {φ(w 1,i )}, φ(c 2 ) := {r, g} \ {φ(w 2,j )}. This leaves at most one monochromatic weak triangle on each of c 1 and c 2 . If such a triangle remains on one of c 1 and c 2 only, then some of (φ(d 1 ), φ(d 2 )) := (g, r) and (φ(d 1 ), φ(d 2 )) := (r, g) surely makes it 2colored. In the other case both d 1 and d 2 occur in two weak triangles; but each d i has only one neighbor in G -D, therefore we must have w 1,1 = w 2,1 = w 1,2 = w 2,2 . Here w 2,1 = w 1,2 holds because otherwise two weak 4-cliques would occur instead of four weak triangles.

If φ(w 2,1 ) = φ(w 1,2 ), a simple completion of the coloring is to put φ(d 1 ) := φ(w 1,2 ) and φ(d 2 ) := φ(w 2,1 ); and if φ(w 2,1 ) = φ(w 1,2 ), then all the four weak triangles have a vertex of opposite color at c 1 or c 2 , and we obtain a weak 2-coloring by assigning (φ(d 1 ), φ(d 2 )) := (g, r). ✷

Based on Lemma 5, the soundness of Algorithm 2 can be verified easily, although it needs a little case distinction because odd hole components in G -D are not weakly 2-colorable. If a component H ≃ K 3 of G -D is an odd cycle longer than three, however, then any edge connecting H with D has to be extendable to a triangle with two vertices in H, for otherwise a claw would occur. Hence, edge e in Step 10 is well-defined, and it induces a strong triangle with c 1 or c 2 . That is, the situation is the same as if the strong triangle occurred from a non-cycle component, and the argument given in the proof of Lemma 5 verifies that all crossing cliques are 2-colored.

Time analysis for Algorithm 2.

As it has been shown, Algorithm 1 called in Step 2 runs within cn 2 i time on any graph of order n i , for some absolute constant c. Observe further that, no matter how many times it is performed during the recursive calls of Step 7, the safe subgraphs occurring in the procedure are mutually vertex-disjoint. Consequently, the overall running time of this part of Algorithm 2 does not exceed cn 2 .

Even better, cycles in Steps 8-13 need time proportional to ℓ, and also those cycles are mutually vertexdisjoint. Hence, they require O(n) time altogether. Also, Step 14 requires constant time for D, because only few crossing cliques can occur and they can be enumerated in constant time. These constants sum up to O(n) through all iterations.

Since the vertex degrees are bounded, we need at most c ′ n time to determine diamond D in Step 4. Also, we can enumerate the components of G -D in Step 5 and check the condition in Step 6 in linear time. Hence, reduction to a smaller problem instance takes linear time. Thus, the overall running time of the algorithm is O(n 2 ). ✷


Michał Kolarz

Włodzimierz Moczurad

Directed figure codes are decidable

Keywords: directed figures, variable-length codes, codicity verification, Sardinas-Patterson algorithm, defect effect

Two-dimensional structures of various kinds can be viewed as generalizations of words. Codicity verification and the defect effect, important properties related to word codes, are studied also in this context. Unfortunately, both are lost in the case of two common structures, polyominoes and figures. We consider directed figures defined as labelled polyominoes with designated start and end points, equipped with catenation operation that uses a merging function to resolve possible conflicts. We prove that in this setting verification whether a given finite set of directed figures is a code is decidable and we give a constructive algorithm. We also clarify the status of the defect effect for directed figures.

Introduction

Codes, i.e., subsets X of a monoid such that every product of the elements decomposes uniquely over X, are a common object of study. Standard variable-length word codes (subsets of a free monoid Σ * , where Σ is an alphabet) are the best-known among them (see e.g. the classic monograph [START_REF] Berstel | Theory of Codes[END_REF]), with properties that have become folklore. This includes the defect effect and the decidability of codicity. Various authors have extended codes to other structures like trees in [START_REF] Mantaci | Codes and equations on trees[END_REF]; [START_REF] Karhumäki | Defect theorems for trees[END_REF] and two-dimensional structures of various kinds like polyominoes in [START_REF] Aigrain | Polyomino tilings, cellular automata and codicity[END_REF]; [START_REF] Beauquier | A codicity undecidable problem in the plane[END_REF]. Whilst the extension to trees preserves the above properties, both are lost in the case of polyominoes. Similar problems arise when considering figures defined as labelled polyominoes. Only a limited version of the defect theorem holds in this case and codicity is decidable for very restricted classes of figures; see a comprehensive study in [START_REF] Harju | Many aspects of defect theorems[END_REF] and also [START_REF] Moczurad | Brick codes: families, properties, relations[END_REF][START_REF] Moczurad | Defect theorem in the plane[END_REF].

Many authors, like [START_REF] Costagliola | On regular drawn symbolic picture languages[END_REF][START_REF] Costagliola | Adding symbolic information to picture models: definitions and properties[END_REF], study other kinds of two-dimensional structures. This interest is driven by obvious applications of picture models in diverse disciplines. Moreover, pictures can be seen as a further natural extension of words. Thus, in the present paper we are interested in codicity testing and the defect effect for yet another kind of pictures.

We consider directed figures defined as labelled polyominoes with designated start and end points. This setting is similar to one of the models, symbolic pixel pictures, described in [START_REF] Costagliola | Adding symbolic information to picture models: definitions and properties[END_REF] and admits a natural definition of catenation. We use the attribute "directed" to emphasize the way figures are catenated; this should not be confused with the meaning of "directed" in e.g. directed polyominoes.

We prove that verification whether a given finite set of directed figures is a code is decidable and we give a constructive algorithm (constructive in the sense that it finds a double factorization of a figure for a non-code). This is a significant change in comparison to previously mentioned picture models. On the other hand, we give several examples to disprove the defect theorem in this case.

Section 2 of the paper defines directed figures and related operations. Then, in Section 3, we give the necessary condition for a set of figures to be a code. We then proceed to the main result of the paper, the decidability of codicity verification, in Section 4. Proof of the main theorem leads to an algorithm which is presented in Section 5. Finally, Section 6 clarifies the status of the defect effect for directed figures. We conclude with some observations and directions for possible further research.

Preliminaries

Throughout the paper Σ is a finite, non-empty alphabet.

A translation in Z 2 by vector u = (u x , u y ) ∈ Z 2 will be denoted by τ u ,

τ u : Z 2 ∋ (x, y) → (x + u x , y + u y ) ∈ Z 2 .
For a set V ⊆ Z 2 and an arbitrary function f : V → Σ it obviously induces

τ u : P (Z 2 ) ∋ V → {τ u (v) | v ∈ V } ∈ P (Z 2 ), τ u : Σ V ∋ f → f • τ -u ∈ Σ τu(V ) . For two points u = (u x , u y ), v = (v x , v y ) ∈ Z 2 and a subset U ⊆ Z 2 , U = ∅ we define dist(u, v) = |u x -v x | + |u y -v y |, dist(U, v) = min u∈U {dist(u, v)}, Γ(U ) = {v ∈ Z 2 | dist(U, v) ≤ 1}.
A set U ⊆ Z 2 is connected if for any x, y ∈ U there exists a sequence x = x 1 , x 2 , . . . , x n , x n+1 = y contained in U such that dist(x i , x i+1 ) = 1 for i ∈ {1, . . . , n}.

domain dom(f ) = D, start point begin(f ) = b, end point end(f ) = e, labelling function label(f ) = l.
Translation vector of f is defined as tran(f ) = end(f )begin(f ). Additionally, we define the empty directed figure ε as (∅, (0, 0), (0, 0), {}), where {} denotes a function with an empty domain.

The set of all directed figures over Σ is denoted by Σ ⋄ . Two directed figures x, y are equal if there exists u ∈ Z 2 such that y = (τ u (dom(x)), τ u (begin(x)), τ u (end(x)), τ u (label(x))).

Thus, we actually consider figures up to a translation.

Example 1 A directed figure and its graphical representation. Each point of the domain, (x, y), is represented by a unit square in R 2 with bottom left corner in (x, y). A circle marks the start point and a diamond marks the end point of the figure. However, since we consider figures up to a translation, we do not mark the coordinates.

({(0, 0), (1, 0), (1, 1)}, (0, 0), (1, 2), {(0, 0) → a, (1, 0) → b, (1, 1) → c})

a ✐ b c ⋄ Definition 2 (Catenation) Let x = (D x , b
x , e x , l x ) and y = (D y , b y , e y , l y ) be directed figures. Catenation of x and y with respect to a merging function m : Σ × Σ → Σ is defined as

x • m y = (D x ∪ τ xe-y b (D y ), b x , τ xe-y b (e y ), l), where l(z) =    l x (z) for z ∈ D x \ τ xe-y b (D y ), τ xe-y b (l y )(z) for z ∈ τ xe-y b (D y ) \ D x , m(l x (z), τ xe-y b (l y )(z)) for z ∈ D x ∩ τ xe-y b (D y ).
When m is fixed, we will write x • y, x • y or simply

xy instead of x • m y. Example 2 a ✐ b c ⋄ • π1 a ✐ b c ⋄ = a ✐ b c a c
⋄ where π 1 denotes projection on the first argument.

Observation 1 Σ ⋄ m = (Σ ⋄ , • m
) is a monoid if and only if m is associative. From now on let m be an arbitrary associative merging function. We will use the notation Σ ⋄ m for both the monoid and the set of directed figures itself. Abusing this notation, we will also write X ⋄ m to denote the set of all figures that can be composed by

• m catenation from figures in X ⊆ Σ ⋄ m . Observation 2 Monoid Σ ⋄
m is never free, since its basis must contain "unit figures" (figures of the type

a E = a ✐ ⋄,a N = a ✐ ⋄ , a W = a ✐ ⋄ , a S = a ✐ ⋄ ,
for all a ∈ Σ), contradicting the freeness.

Example 3 Regardless of the merging function, the following figure can be decomposed as e.g.

a N a N a E a S a S a E a N a N a E and a E a E a N a W a W a N a E a E a E . a ✐ a a a a a a a a ⋄ 3 Necessary condition for codicity Definition 3 (Code) X ⊆ Σ ⋄ m is a code if for any x 1 , . . . , x k , y 1 , . . . , y l ∈ X the equality x 1 • m . . . • m x k = y 1 • m . . . • m y l implies k = l and x i = y i for each i ∈ {1, . . . , k}. Example 4 It is clear that X = { a ✐ ⋄, a ✐ ⋄ } ⊆ {a} ⋄ π1 is a code because the figures are directed in the plane. Example 5 X = {w = a ✐ a ⋄ , x = a ✐ a ⋄,y = a ✐ a ⋄ , z = a ✐ a ⋄ } ⊆ {a} ⋄ π1 is not a code since wx = yz = a ✐ a a a ⋄ . Theorem 1 (Necessary condition) Let X = {x 1 , . . . , x n } ⊆ Σ ⋄ m . If there exist α i1 , . . . , α i k ∈ Z + , where {i 1 , . . . , i k } ⊆ {1, . . . , n}, such that k j=1 α ij tran(x ij ) = (0, 0), then X is not a code. Proof: Let x = x i1 • • • x i1 αi 1 x i2 • • • x i2 αi 2 • • • x i k • • • x i k αi k
. Now consider the following set of directed figures:

Y = {x i } ∞ i=1 .
Since tran(x) = (0, 0), every element of Y has the same domain. There is only a finite number of possible labellings of this domain, which implies that regardless of the merging function and labelling of x, there exist a, b ∈ N, a = b such that x a = x b . Hence X is not a code; cf. Examples 9 and 10. ✷

Observation 3 Let v 1 , . . . , v k ∈ Z 2 .
Following conditions are equivalent (• denotes the usual dot product):

1. i α i v i = 0 for all α 1 , . . . , α k ∈ Z + , 2. there exists v ∈ Z 2 such that v • v i > 0 for all i, i.e.
, there exists a line passing through (0, 0) such that all v i 's lie on one side of it.

• • ✲ w v w + v

Decidability of verification

In this section we prove that testing whether a given set of figures is a code is decidable. We begin with observations that allow us to construct a "bounding area" for figures. We then proceed with properties that imply finiteness of possible configuration sets and, consequently, decidability of the problem in question.

Let X = {x 1 , . . . , x n } ⊆ Σ ⋄ m . Either there exists a vector τ E ∈ Z 2 such that for all x ∈ X τ E • tran(x) > 0
or, by Theorem 1, X is not a code. If τ E exists, we can take it to be long enough so that for all x ∈ X dom(x) ∪ {end(x)} ⊆ HP (τ E , begin(x)),

where, for given v, w ∈ R 2 , HP (v, w)

denotes a half-plane {u ∈ Z 2 | v • (u -(w + v)) ≤ 0}. Observe that this implies dom(x) ∪ {end(x)} ⊆ HP (τ E , end(x))
for all x ∈ X. Without loss of generality we can assume

∠(R -π 2 (τ E ), tran(x 1 )) ≤ ∠(R -π 2 (τ E ), tran(x 2 )) ≤ . . . ≤ ∠(R -π 2 (τ E ), tran(x n
)) (where R φ denotes a rotation by φ and ∠ is the angle spanned by two vectors) and begin(x) = (0, 0) for all x ∈ X. Now choose constants r S , r N , r W > 0 such that the vectors

τ N = r N R π 2 (tran(x n )), τ W = -r W τ E , τ S = r S R -π 2 (tran(x 1 ))
define a "bounding area" for figures in X, i.e., for all x ∈ X dom(x) ∪ {end(x)} ⊆

τ ∈{τ N ,τ W ,τ S }
{HP (τ, begin(x))}.

Figure 2 shows half-planes HP (τ, begin(x)) for τ ∈ {τ E , τ N , τ W , τ S }.

For x ∈ X ⋄ m define CE + (x) = HP (τ S , end(x)) ∩ HP (τ N , end(x)) ∩ HP (τ W , end(x)), CE -(x) = Z 2 \ CE + (end(x)), CW + (x) = v {v + (CE + (end(x)) ∩ HP (τ E , end(x)))}, CW -(x) = Z 2 \ CW + (end(x)),
where the union in the definition of CW + (x) is taken over v ∈ Z 2 lying within an angle spanned by vectors -tran(x 1 ) and -tran(x n ).

The following properties are now immediately proven:

Proposition 1 For all x, y ∈ X ⋄ m labels of CE -(x) cannot be overwritten in xy, i.e., u ∈ CE -(x) ∩ dom(x) ⇒ label(x)(u) = label(xy)(u), u ∈ CE -(x) \ dom(x) ⇒ u ∈ dom(xy). Proposition 2 For all x ∈ X ⋄ m labels of CW -(x) are not defined in x, i.e., u ∈ CW -(x) ⇒ u ∈ dom(x). Proposition 3 For all x, y ∈ X ⋄ m CE + (xy) ⊆ CE + (x).
Proposition 4 For all x, y ∈ X ⋄ m CW + (x) ⊆ CW + (xy).

We define a configuration as a pair (x, y), with x, y ∈ X ⋄ m . We say that (x ′ , y ′ ) ∈ (X ⋄ m ) 2 is a successor of (x, y) and write (x, y) ≺ (x ′ , y ′ ) if

x ′ = xx ′′ for some x ′′ ∈ X and y = y ′ , or y ′ = yy ′′ for some y ′′ ∈ X and x = x ′ .

By ≺ * we denote the transitive closure of ≺. Obviously X is not a code if and only if there exist x, y ∈ X and z ∈ X ⋄ m such that x = y and (x, y) ≺ * (z, z). Our goal is either to find a configuration (x, y) such that x = y and (x, y) ≺ . . . ≺ (z, z) (then X is not a code), or to prove that such a configuration does not exist (then X is a code). A configuration satisfying the above condition will be called an eventually terminating configuration.

Unfortunately, there are potentially infinitely many configurations to check. The following propositions will let us reduce the number of configurations under consideration. Proposition 5 If (x, y) is eventually terminating and (x ′ , y ′ ) ≺ (x, y), then (x ′ , y ′ ) is eventually terminating.

✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ✟ ✟ ✟ ✟ ✟ ✟ • ✲ τ E ❆ ❆ ❆ ❑ τ N ✛ τ W ✠ τ S HP (τ E , begin(x)) ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❅ ❅ ❅ ❅ ❅ ❅ ✟ ✟ ✟ ✟ ✟ ✟ • ✲ τ E ❆ ❆ ❆ ❑ τ N ✛ τ W ✠ τ S HP (τ N , begin(x)) ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ✟ ✟ ✟ ✟ ✟ ✟ • ✲ τ E ❆ ❆ ❆ ❑ τ N ✛ τ W ✠ τ S HP (τ W , begin(x)) ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ✟ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ✟ ✟ ✟ ✟ ✟ ✟ • ✲ τ E ❆ ❆ ❆ ❑ τ N ✛ τ W ✠ τ S HP (τ S , begin(x))
❅ ❅ ❅ ❅ ❅ ❅ ✟ ✟ ✟ ✟ ✟ ✟ • ❅ ❅ ❅ ✟ ✟ ✟ ✟ ✟ ✟ ❅ ❅ ❅ ❅ ✟ ✟ ✟ ✟ ✟ ✟ CW + (x) CE + (x)
Proof: Obvious. ✷ Proposition 6 If (x, y) is eventually terminating, then

end(x) ∈ CW + (y) ∪ CE + (y), end(y) ∈ CW + (x) ∪ CE + (x).
Proof: See definitions of CW + and CE + . ✷ Proposition 7 If (x, y) is eventually terminating, then

label(x) | CE -(x)∩CE -(y) ≡ label(y) | CE -(x)∩CE -(y) .
Proof: See definition of CE -and Proposition 1. ✷ Notice that we do not need all of the information contained in configurations, just those labellings that can be changed by future catenations. By Proposition 7, instead of (x, y) we can consider a reduced configuration defined as a pair (π RC (x, y), π RC (y, x)) where

π RC (z, z ′ ) = (end(z), label(z) | dom(z)\(CE -(z)∩CE -(z ′ )) ).
Now Proposition 5 implies that we need only consider configurations where the span along τ E is bounded by |τ E |, i.e., |τ E • (end(x)end(y))| ≤ |τ E | 2 , since no single figure advances end(x) or end(y) by more than |τ E |. Moreover, Proposition 6 restricts the perpendicular span (in the direction of R -π 2 (τ E )). Hence the number of reduced configurations, up to translation, is finite. This leads us to the main theorem of the paper:

Theorem 2 It is decidable whether a given finite set X ⊆ Σ ⋄ m is a code.

Algorithm

From the proof of Theorem 2 we can obtain an algorithm that verifies whether a given set of directed figures is a code. The following procedure returns true if the given input set is a code; otherwise it returns false. Additionally, if the given set is not a code, the algorithm finds x 1 , . . . ,

x k , x ′ 1 , . . . , x ′ l such that x 1 • • • x k = x ′ 1 • • • x ′ l .
Note that this is the reason for processing configurations (and not just reduced configurations) within the main loop of the algorithm. iii. if (x, yz) may be eventually terminating

1. input X = {x 1 , . . . , x n } ⊆ Σ ⋄ m ; 2. if there exist α i1 , . . . , α i k ∈ Z + ({i 1 , . . . , i k } ⊆ {1, . . . , n}) such that n j=1 α ij tran(x ij ) = (0, 0) then return false; 3. compute τ E , τ W , τ S , τ N ; 4. set C = ∅ (set of checked configurations), RC = ∅ (set of checked reduced configurations); 5. for each x, y ∈ {τ -begin(x) (x) | x ∈ X}, x = y do
and |τ E • (end(x) -end(yz))| ≤ |τ E | 2 and (π RC (x, yz), π RC (yz, x)) ∈ RC then set C = C ∪ {(x, yz)}, RC = RC ∪ {(π RC (x, yz), π RC (yz, x))};
8. return true;

Note that configurations are considered up to a translation; in particular, this applies to ". . . ∈ RC" tests.

Observe that the actual implementation may omit the RC T M P set and use C = ∅ as the loop condition (a new element is added to C if and only if a new element is added to RC). This would improve the efficiency but would obliterate the similarity of the algorithm to the algorithm of Sardinas and Patterson, c.f. Example 8. The implementation can also make use of the symmetrical nature of configurations.

The following examples show the algorithm behaviour for a code and a non-code. For the sake of simplicity, we depict elements of the set C only and we omit steps containing obvious assignments. We also omit pairs that can be obtained from another pair by exchanging the elements.

Example 6 Consider X = {x = ✐ ⋄ a , y = ✐ ⋄ a } ⊆ {a} ⋄ π1 .
Step 2: The condition clearly fails.

Step 3: Set τ E = (1, 1), τ W = (-ǫ, -ǫ), τ S = (0, -ǫ), τ N = (-ǫ, 0), where ǫ is a small positive constant less than √ 2/2. A larger value of ǫ would force the algorithm to overestimate the bounding area and thus process too many configurations.

Step 5: C = {(x, y)}.

Step 7: C is already empty after first iteration, since all candidate configurations, i.e., (xx, y), (x, yx), (xy, y) and (x, yy), fail the condition of Proposition 7.

Step 8: Thus X is a code.

Example 7 Consider X = {w = a ✐ a ⋄ , x = a ✐ a ⋄,y = a ✐ a ⋄ , z = a ✐ a ⋄ } ⊆ {a} ⋄ π1 .
Step 2: The condition fails.

Step 3: Set

τ E = (1, 1), τ W = (-1 2 , -1 2 ), τ S = (0, -1), τ N = (-1 2 , 0).
Step 5: C = {(w, x), (w, y)}; other pairs fail the condition of Proposition 7.

Step 7, iteration 1: C = {(ww, x), (ww, y), (wx, y), (wz, y)}.

Step 7, iteration 2: One of configurations gives wx = yz, hence X is not a code.

The final example illustrates the similarity of the algorithm presented here to the well-known algorithm of Sardinas and Patterson (ASP) when figures resemble words.

Example 8 Consider X = {x = a ✐ a ⋄,y = b ✐ ⋄,z = b ✐ a ⋄} ⊆ {a, b} ⋄ π1 .
Step 2: The condition fails.

Step 3: Set τ E = (2, 0), τ W = (-1 2 , 0), τ S = (0, -1 2 ), τ N = (0, 1 2 ).

Step 5: C = {(y, z)}; other pairs fail the condition of Proposition 7. The respective reduced configuration, formally (((1, 0), {}), ((2, 0), {(1, 0) → a})), corresponds to the -a suffix computed by ASP.

Step 7, iteration 1: C = {(y, zy)}; other pairs fail various conditions: (yx, z) fails the ". . . ∈ RC" test, (yy, z) and (yz, z) fail the condition of Proposition 7; (y, zx) and (y, zz) fail the τ E -span condition. Note a small dissimilarity with ASP, which is a consequence of extending configurations from both sides. This could be optimized by always extending only the "leftmost" component with respect to the τ E direction.

Step 7, iteration 2: C = ∅, hence X is a code.

Observe that the RC set of the algorithm corresponds to the union of sets constructed by ASP in each step.

Defect effect

In this section we present several counterexamples to disprove the defect theorem for directed figures. They show that the effect fails even for very simple sets. On the other hand, restricting figures to wordlike shapes, with appropriately chosen start and end points, obviously guarantees the defect property. It would be interesting to characterize what restrictions on figures allow the defect effect to hold.

Theorem 3 (Classical defect effect) Let X ⊆ Σ + be a non-code. There exists Y ⊆ Σ + such that |Y | < |X| and X + ⊆ Y + .

Let us now consider the following examples:

Example 9 Let Σ = {a}, m = {(a, a) → a} and

X = {x = a ✐ ⋄,y = a ✐ ⋄ }. For each n ≥ 1 (xy) n = a ✐ ⋄ a
which implies that X is not a code. However, there exists no Y such that |Y | < 2 and X + ⊆ Y + .

Thus, the defect effect does not hold even for two squares. The following example shows that in fact this is even worse: there are singleton non-codes.

Example 10 Let Σ = {a}, m = {(a, a) → a} and

X = { a ✐ ⋄} For each n ≥ 1 x n = x
which implies that X is not a code. However, there exists no Y such that |Y | < 1 and X + ⊆ Y + .

The defect theorem does not hold even for non-codes that do not allow a word x with tran(x) = (0, 0) to be composed: ⋄ a which implies that X is not a code. However, there exists no Y such that |Y | < 2 and X + ⊆ Y + .

Final remarks

It is interesting to note that the complexity of the codicity verification algorithm depends on the angle spanned by the translation vectors of figures. Bigger angles result in higher complexity, since there are more configurations to check. The obvious upper bound is exponential in the size of "bounding areas" defined in Section 4; this in turn grows like tan(α/2), where α is the angle in question. However, at α = π the complexity drops radically because of Theorem 1. At the other end of spectrum, when the angle tends to zero, the figures resemble words and the algorithm becomes similar to the Sardinas and Patterson's algorithm, cf. Example 8. Estimating the complexity is an obvious subject for further research. An interesting extension of our results would be to consider figures with no merging function, where catenation is a partial operation defined for those figures that do not overlap when catenated. Additional restrictions on figures would have to be imposed (e.g., starting point on the inner boundary and end point on the outer boundary of a figure).

Another direction for further study is the behaviour of infinite catenations, like the usual infinite word asymptotics (cf. [START_REF] Foryś | Asymptotic behaviour of bi-infinite words[END_REF]), and the density of codes (cf. [START_REF] Moczurad | Asymptotic density of brick and word codes[END_REF]).

Definition 1 (

 1 Directed figure) Let D ⊆ Z 2 be finite and connected, b ∈ D, e ∈ Γ(D) and l : D → Σ. A quadruple f = (D, b, e, l) is called a directed figure (over Σ) with

Fig. 1 :

 1 Fig. 1: A half-plane HP (v, w).

Fig. 2 :

 2 Fig. 2: Half-planes HP (τ, begin(x)) for τ ∈ {τE, τN , τW , τS}; the black dot denotes the start point of x.

Fig. 3 :

 3 Fig. 3: CW + (x) and CE + (x) regions; the black dot denotes the end point of x.

  (a) if (x, y) may be eventually terminating (i.e., conditions from Propositions 6 and 7 are satisfied) and (π RC (x, y), π RC (y, x)) ∈ RC then set C = C ∪ {(x, y)}, RC = RC ∪ {(π RC (x, y), π RC (y, x))}; 6. set RC T M P = ∅; 7. while RC = RC T M P do (a) set C T M P = C, RC T M P = RC, C = ∅; (b) for each (x, y) ∈ C T M P and z ∈ X do i. if xz = y or x = yz then return false; ii. if (xz, y) may be eventually terminating and |τ E • (end(xz)end(y))| ≤ |τ E | 2 and (π RC (xz, y), π RC (y, xz)) ∈ RC then set C = C ∪ {(xz, y)}, RC = RC ∪ {(π RC (xz, y), π RC (y, xz))};

Example 11

 11 Let Σ = {a, b, c}, m = {(a, •) → a, (•, a) → a, . . .} (the remaining values of m can be set arbitrarily) and X = {x = a ✐ b ⋄ a , y = a ✐ c ⋄ a }. Then xy = yx = a ✐ a a