François Dross
email: francois.dross@googlemail.com

Florent Foucaud
email: florent.foucaud@gmail.fr

Valia Mitsou
email: vmitsou@liris.cnrs.fr

Pascal Ochem
email: pascal.ochem@lirmm.fr

Théo Pierron
email: theo.pierron@labri.fr

Complexity of planar signed graph homomorphisms to cycles

Keywords: signed graph, edge-coloured graph, graph homomorphism, planar graph

We study homomorphism problems of signed graphs from a computational point of view. A signed graph is an undirected graph where each edge is given a sign, positive or negative. An important concept when studying signed graphs is the operation of switching at a vertex, which is to change the sign of each incident edge. A homomorphism of a graph is a vertex-mapping that preserves the adjacencies; in the case of signed graphs, we also preserve the edge-signs. Special homomorphisms of signed graphs, called s-homomorphisms, have been studied. In an s-homomorphism, we allow, before the mapping, to perform any number of switchings on the source signed graph. The concept of s-homomorphisms has been extensively studied, and a full complexity classification (polynomial or NPcomplete) for s-homomorphism to a fixed target signed graph has recently been obtained. Nevertheless, such a dichotomy is not known when we restrict the input graph to be planar, not even for non-signed graph homomorphisms.

We show that deciding whether a (non-signed) planar graph admits a homomorphism to the square C 2 t of a cycle with t 6, or to the circular clique K 4t/(2t-1) with t 2, are NP-complete problems. We use these results to show that deciding whether a planar signed graph admits an s-homomorphism to an unbalanced even cycle is NP-complete. (A cycle is unbalanced if it has an odd number of negative edges). We deduce a complete complexity dichotomy for the planar s-homomorphism problem with any signed cycle as a target.

We also study further restrictions involving the maximum degree and the girth of the input signed graph. We prove that planar s-homomorphism problems to signed cycles remain NP-complete even for inputs of maximum degree 3 (except for the case of unbalanced 4-cycles, for which we show this for maximum degree 4). We also show that for a given integer g, the problem for signed bipartite planar inputs of girth g is either trivial or NP-complete.

Introduction

In this paper, we study the computational complexity of graph and signed graph homomorphism problems. Our main focus is the case where the inputs are planar and the targets are cycles (but we also consider other cases). Homomorphisms are structure-preserving mappings between discrete structures; this type of problems is very general and models many combinatorial problems. Consequently, the study of the algorithmic properties of homomorphism problems is a rich area of research that has gained a lot of attention. We refer to the book [START_REF] Hell | Graphs and Homomorphisms[END_REF] as a reference on graph homomorphism problems.

An edge-coloured graph is a graph with several types of (undirected) edges: each type corresponds to a colour. Given two edge-coloured graphs G and H, a homomorphism of G to H is a vertex-mapping f of V (G) to V (H) that preserves adjacencies and edge-colours, that is, if x and y are adjacent via a c-coloured edge in G, then f (x) and f (y) must be adjacent via a c-coloured edge in H as well. When such a homomorphism exists, we write G → H. This concept is studied for example in [START_REF] Alon | Homomorphisms of edge-colored graphs and Coxeter groups[END_REF][START_REF] Brewster | Vertex colourings of edge-coloured graphs[END_REF][START_REF] Hell | On nice graphs[END_REF][START_REF] Montejano | Homomorphisms of 2-edgecolored graphs[END_REF][START_REF] Ochem | Homomorphisms of 2-edge-colored triangle-free planar graphs[END_REF]. In this language, standard undirected graphs can simply be seen as 1-edge-coloured graphs. Signed graphs are a special type of 2-edge-coloured graphs whose edge-colours are signs: positive and negative. In this paper, we will consider two types of objects: standard undirected graphs (that will simply be called (1-edge-coloured) graphs), and signed graphs.

Computational homomorphism problems. The most fundamental class of algorithmic homomorphism problems is the following one (where H is any fixed edge-coloured graph):

Hom(H) Instance: An (edge-coloured) graph G. Question: Does G admit a homomorphism to H? Problem Hom(H) has been studied for decades. For example, consider 1-edge-coloured graphs, and denote the 3-vertex complete graph by K 3 . Then, Hom(K 3 ) is the classic 3-Colouring problem, shown NP-complete by Karp [START_REF] Karp | Reducibility among combinatorial problems[END_REF]. (More generally, a proper t-colouring of a graph G is a homomorphism to the complete graph K t .) Hom(H) for edge-coloured graphs is studied for example in [START_REF] Brewster | Vertex colourings of edge-coloured graphs[END_REF][START_REF] Brewster | The complexity of colouring symmetric relational systems[END_REF][START_REF] Brewster | The complexity of signed graph and edgecoloured graph homomorphisms[END_REF][START_REF] Brewster | On homomorphisms to edge-coloured cycles[END_REF][START_REF] Movarraei | Oriented, 2-edge-colored, and 2-vertex-colored homomorphisms[END_REF].

Hom(H) is also studied under the name of Constraint Satisfaction Problem (CSP), see for example [START_REF] Feder | The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory[END_REF]. In this setting, edge-coloured graphs are seen as structures coming with a number of symmetric binary relations (one for each edge-colour). In the context of CSPs, one also considers discrete relational structures that may have relations of arbitrary arities. The celebrated Dichotomy Conjecture of Feder and Vardi [START_REF] Feder | The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory[END_REF] and the subsequent work aims at classifying the complexity of general CSP problems. While the conjecture was recently solved in [START_REF] Bulatov | A dichotomy theorem for nonuniform CSPs[END_REF][START_REF] Zhuk | A Proof of CSP Dichotomy Conjecture[END_REF] (independently) using the tools and language of universal algebra, this algebraic formulation does not always provide simple explicit descriptions of the dichotomy. Thus, obtaining explicit dichotomy classifications for relevant special cases is still of major interest.

When studying Hom(H), we may always restrict ourselves to edge-coloured graphs H that are cores: H is a core if it does not have any homomorphism to a proper subgraph of itself (in other words, all of its endomorphisms are automorphisms). Moreover, the core of an edge-coloured graph H, noted core(H), is the smallest subgraph of H that is a core. It is well-known that the core of an edge-coloured graph is unique (up to isomorphism). It is not difficult to observe that the complexity of Hom(H) is the same as the one of Hom(core(H)). For more details on these notions see the book [START_REF] Hell | Graphs and Homomorphisms[END_REF].

One of the most fundamental results in the area of CSP dichotomies is the one obtained for 1edge-coloured graphs by Hell and Nešetřil. They proved in [START_REF] Hell | On the complexity of H-coloring[END_REF] that if the core of an undirected graph H has at least two edges, Hom(H) is NP-complete, and polynomial-time otherwise. (Note that the latter condition equates to say that H is bipartite or has a loop, a property that is easily testable.) One may ask the following natural question: what is the behaviour of the above dichotomy for specific restrictions of the input graphs? Planar instances. Colouring and homomorphism problems are studied extensively for the class of planar graphs. One consequence of the Four Colour Theorem (that any planar graph is properly 4colourable) is that, contrarily to the general case, Hom(K 4 ) is trivially polynomial-time solvable for planar instances. In this paper, we will study the following restriction of Hom(H):

Planar Hom(H) Instance: A planar (edge-coloured) graph G. Question: Does G admit a homomorphism to H? A complexity dichotomy for Planar Hom(H) in the case of 1-edge-coloured graphs, if it exists, is probably not as easy to describe as the Hell-Nešetřil dichotomy for Hom(H). Planar Hom(H) is known to be NP-complete for H = K 3 [START_REF] Garey | Computers and intractability: a guide to the theory of NPcompleteness[END_REF], but, as mentioned before, it is trivially polynomial-time when H contains a 4-clique. There are other non-trivial examples that are polynomial-time. For example, consider the Clebsch graph C 16 , a remarkable triangle-free graph of order 16. It follows from [START_REF] Guenin | Packing T-joins and edge-colouring in planar graphs[END_REF][START_REF] Naserasr | Homomorphisms and edge-coloring of planar graphs[END_REF] that every triangle-free planar graph has a homomorphism to C 16 . Since C 16 itself has no triangle, a planar graph maps to C 16 if and only if it is triangle-free, and thus Planar Hom(C 16 ) is polynomial-time solvable. Infinitely many such examples are known, see [START_REF] Hell | Complexity of planar homomorphisms[END_REF][START_REF] Nešetřil | Tree-depth, subgraph colorings and homomorphism bounds[END_REF].

Planar Hom(H) for 1-edge-coloured graphs was studied more extensively in [START_REF] Hell | Complexity of planar homomorphisms[END_REF][START_REF] Macgillivray | On the complexity of H-colouring planar graphs[END_REF], where it was independently proved to be NP-complete when H is any odd cycle C 2k+1 , via two different techniques. It is also proved in [START_REF] Macgillivray | On the complexity of H-colouring planar graphs[END_REF] that Planar Hom(H) is NP-complete whenever H is subcubic and has girth 5. Planar Hom(H) is also proved NP-complete in [START_REF] Hell | Complexity of planar homomorphisms[END_REF] when H is an odd wheel, or the Penny graph.

Further instance restrictions. The difficulty of classifying the complexity of Planar Hom(H) makes it meaningful to further refine the pool of graph instances to be examined. For example, restrictions on the maximum degree are studied in [START_REF] Galluccio | The complexity of H-coloring of bounded degree graphs[END_REF][START_REF] Siggers | Dichotomy for bounded degree H-colouring[END_REF]. In [START_REF] Siggers | Dichotomy for bounded degree H-colouring[END_REF], it is proved that for every undirected non-bipartite graph H, there is an integer b(H) such that Hom(H) is NP-complete for graphs of maximum degree b(H). The value of b(H) can be arbitrarily large, but for many graphs H, b(H) = 3 [START_REF] Siggers | Dichotomy for bounded degree H-colouring[END_REF]. In particular, it is proved in [START_REF] Galluccio | The complexity of H-coloring of bounded degree graphs[END_REF] that for all k ≥ 1, b(C 2k+1 ) = 3, that is, Hom(C 2k+1 ) is NP-complete for subcubic graphs. In fact, the result from [START_REF] Galluccio | The complexity of H-coloring of bounded degree graphs[END_REF] (combined with [START_REF] Hell | Complexity of planar homomorphisms[END_REF][START_REF] Macgillivray | On the complexity of H-colouring planar graphs[END_REF]) also implies that Planar Hom(C 2k+1 ) is NP-complete for subcubic graphs.

Other restrictions are on the girth of the input graph, that is, the smallest length of a cycle. It is known that for any k ≥ 1, there is an integer g = g(k) such that all planar graphs of girth at least g admit a homomorphism to C 2k+1 [START_REF] Galluccio | High-girth graphs avoiding a minor are nearly bipartite[END_REF]. A restriction to planar graphs of a conjecture of Jaeger [START_REF] Jaeger | Nowhere-zero flow problems[END_REF] implies that g(k) = 4k, and it is known that 4k ≤ g(k) ≤ (20k -2)/3 [START_REF] Borodin | Homomorphisms from sparse graphs with large girth[END_REF]. In [START_REF] Esperet | A complexity dichotomy for the coloring of sparse graphs[END_REF], it is proved that for every fixed k ≥ 2 and g ≥ 3, either every planar graph of girth at least g maps to C 2k+1 , or Planar Hom(C 2k+1 ) is NP-complete for such graphs. Other examples of this type of "hypothetical complexity" theorems exist in other contexts, see for example [START_REF] Feder | On Barnette's conjecture[END_REF][START_REF] Kochol | Hypothetical complexity of the nowherezero 5flow problem[END_REF].

Signed graphs and switching homomorphisms. Signed graphs are special types of 2-edge-coloured graphs, whose edge-colours represent signs: positive and negative. Formally, a signed graph is a pair (G, σ), where G is the underlying graph (the graph containing both the positive and the negative edges) and σ : E(G) → {-1, +1} is the sign function that describes the edge-signs. Signed graphs were studied as early as the 1930's in the first book on graph theory by König [START_REF] König | Theorie der endlichen und unendlichen Graphen[END_REF]. They were rediscovered in the 1950's by Harary [START_REF] Harary | On the notion of balance of a signed graph[END_REF], who introduced the name signed graph and applied them to the area of social psychology. The concept was later developed by Zaslavsky in [START_REF] Zaslavsky | Signed graphs[END_REF] and numerous subsequent papers [START_REF] Zaslavsky | Characterizations of signed graphs[END_REF][START_REF] Zaslavsky | Signed graphs[END_REF][START_REF] Zaslavsky | Signed graph coloring[END_REF][START_REF] Zaslavsky | Chromatic invariants of signed graph[END_REF][START_REF] Zaslavsky | How colorful the signed graph?[END_REF] and has become an important part of combinatorics, with many connections to deep results and conjectures. See [START_REF] Zaslavsky | A mathematical bibliography of signed and gain graphs and allied areas[END_REF] for a dynamic bibliography on the topic.

Zaslavsky [START_REF] Zaslavsky | Signed graphs[END_REF] introduced the switching operation: given a signed graph G and a vertex v, to switch at v is to change the sign of all edges incident to v (this can be seen as multiplying their signs by -1). We say that two signed graphs G and G ′ are switching-equivalent if G ′ can be obtained from G by any sequence of switchings. Note that one can test switching-equivalence in polynomial time (on labelled graphs), see [START_REF] Brewster | The complexity of signed graph and edgecoloured graph homomorphisms[END_REF][START_REF] Zaslavsky | Signed graphs[END_REF].

The switching operation turns out to be important in the context of graph minors, and it relates to some outstanding problems in graph theory, see [START_REF] Guenin | Packing odd circuit covers: a conjecture[END_REF][START_REF] Naserasr | Homomorphisms of planar signed graphs to signed projective cubes[END_REF][START_REF] Naserasr | Homomorphisms of signed graphs[END_REF] for details. In this context, Guenin introduced in [START_REF] Guenin | Packing odd circuit covers: a conjecture[END_REF] a special kind of homomorphisms of signed graphs, whose theory was later developed in [START_REF] Naserasr | Homomorphisms of planar signed graphs to signed projective cubes[END_REF][START_REF] Naserasr | Homomorphisms of signed graphs[END_REF]. Following the terminology in [START_REF] Brewster | The complexity of signed graph and edgecoloured graph homomorphisms[END_REF], we define an s-homomorphism of a signed graph G to a signed graph H as a vertex-mapping f from V (G) to V (H) such that there exists a signed graph G ′ that is switching-equivalent to G, and f is a classic edge-coloured graph homomorphism of G ′ to H. (Note that additionally one may allow switching at H; this does not change the problem, and we will generally not do so, but we can fix a convenient switching-equivalent sign function of H and stick to it.) When an s-homomorphism exists, we note G s -→ H.

Similarly to edge-coloured graph homomorphism, we say that a signed graph G is an s-core if G admits no s-homomorphism to a proper signed subgraph of itself, and the s-core of G is the smallest subgraph of G that is an s-core (it is unique up to s-isomorphism and switching [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF]).

We next define the decision problem that corresponds to s-homomorphisms (with H a fixed signed graph).

s-Hom(H)

Instance: A signed graph G. Question: Does G admit an s-homomorphism to H? Note that for two switching-equivalent signed graphs H and H ′ , the definition of an s-homomorphism implies that s-Hom(H) and s-Hom(H ′ ) have the same complexity.

Extending the Hell-Nešetřil dichotomy [START_REF] Hell | On the complexity of H-coloring[END_REF] for Hom(H) for 1-edge-coloured graph problems, a complexity dichotomy for s-Hom(H) problems was proved in the papers [START_REF] Brewster | The complexity of signed graph and edgecoloured graph homomorphisms[END_REF][START_REF] Brewster | A complexity dichotomy for signed H-colouring[END_REF]. The authors showed that if the s-core of a signed graph H has at least three edges, then s-Hom(H) is NP-complete; it is polynomial-time otherwise. On the other hand, it was shown in [START_REF] Brewster | The complexity of signed graph and edgecoloured graph homomorphisms[END_REF] that a similar dichotomy for Hom(H) problems for signed graphs (that is, 2-edge-coloured graphs and no switching allowed), is as difficult to obtain as the one for general CSPs. This indicates that it probably cannot be stated in simple graph-theoretic terms.

The authors of [START_REF] Brewster | The complexity of signed graph and edgecoloured graph homomorphisms[END_REF] asked what is the complexity of s-Hom(H) problems when the input is planar. Let us define the corresponding analogue of Planar Hom(H).

Planar s-Hom(H)

Instance: A planar signed graph G. Question: Does G admit an s-homomorphism to H?

An interesting case is the one when H = (C k , σ) is a cycle (k ≥ 3). If H is switching-equivalent
either to an all-positive C k , or to an all-negative C k , then the complexity of s-Hom(H) and Planar s-Hom(H) are the same as the ones of Hom(C k ) and Planar Hom(C k ), respectively [START_REF] Brewster | The complexity of signed graph and edgecoloured graph homomorphisms[END_REF]. When k is odd, one of these two cases holds, and thus by the results of [START_REF] Hell | Complexity of planar homomorphisms[END_REF][START_REF] Macgillivray | On the complexity of H-colouring planar graphs[END_REF], in that case Planar s-Hom(H) is NP-complete.

To state the situation when k is even, it is convenient to introduce the notion of balance: a signed graph is balanced if every cycle contains an even number of negative edges. This central notion is already present in the work of König [START_REF] König | Theorie der endlichen und unendlichen Graphen[END_REF] but was theorized by Harary [START_REF] Harary | On the notion of balance of a signed graph[END_REF].

If k = 2t is even and H = (C k , σ) is balanced, H is switching-equivalent to a positive 2-vertex complete graph and thus Planar s-Hom(H) is polynomial-time. When H is unbalanced, by switching H if necessary, we may assume that H has a unique negative edge and denote this signed graph by U C 2t . Then, s-Hom(U C 2t ) has been proved to be NP-complete [START_REF] Brewster | The complexity of signed graph and edgecoloured graph homomorphisms[END_REF][START_REF] Foucaud | The complexity of homomorphisms of signed graphs and signed constraint satisfaction[END_REF], but the complexity of Planar s-Hom(U C 2t ) is not known. We settle this question in this paper.

We point out that homomorphisms of non-signed graphs to odd cycles are an important topic in the theory of homomorphisms and circular colourings. Odd cycles are among the simplest nontrivial graphs (with respect to homomorphisms) and are fundamental in the study of graph colourings. Several well-studied open questions and conjectures involving homomorphisms to odd cycles exist in the area, such as Jaeger's conjecture and others (see [START_REF] Borodin | Homomorphisms from sparse graphs with large girth[END_REF][START_REF] Esperet | A complexity dichotomy for the coloring of sparse graphs[END_REF] for more details). For s-homomorphisms of bipartite signed graphs, unbalanced even cycles play a similar role as odd cycles for homomorphisms of non-signed graphs. Here also, certain interesting conjectures and theorems are stated, see [START_REF] Charpentier | Homomorphisms of sparse signed graphs[END_REF] for a recent study. This motivates the study of the complexity of s-homomorphisms to cycles.

Our results. Our main goal is to prove that Planar s-Hom(U C 2k ) is NP-complete whenever k ≥ 2. As a first step, in Section 3, we study non-signed graphs. We prove that Planar Hom(H) is NPcomplete when H is the square of a cycle; in turn, this is used to prove that Planar Hom(H) is NP-complete when H is a cubic circular clique. In Section 4, we use these results to prove that Planar s-Hom(U C 2k ) is NP-complete whenever k ≥ 3. In Section 5, using a different technique, we prove that the case k = 2 is also NP-complete. In Section 6, we show that for every integer k ≥ 1 and even integer g ≥ 2, either every planar bipartite signed graph of girth g admits a homomorphism to U C 2k , or Planar s-Hom(U C 2k ) is NP-complete for planar bipartite inputs of girth g. In Section 7, we show that the results of Section 4 also apply to subcubic input signed graphs (except for U C 4 , for which this holds for maximum degree 4). We first start with some preliminary considerations in Section 2.

Preliminaries

This section gathers some preliminary considerations.

Some definitions

Given a graph G, the square of G, denoted G 2 , is the graph obtained from G by adding edges between all vertices at distance 2.

Given two integers p and q with gcd(p, q) = 1, the circular clique K p/q is the graph on vertex set {k 0 , . . . , k p-1 } with k i adjacent to k j if and only if q ≤ |i -j| ≤ p -q. Circular cliques are defined in the context of circular chromatic number, see for example [START_REF] Zhu | Planar graphs with circular chromatic numbers between 3 and 4[END_REF].

Switching graphs

We now describe a construction that is important when studying s-homomorphisms.

Definition 2.1. Let G be a signed graph. The switching graph of G is a signed graph denoted ρ(G) and constructed as follows.

(i) For each vertex u in V (G) we have two vertices u 0 and u 1 in ρ(G).

(ii) For each edge e between u and v in G, we have four edges between u i and v j (i, j ∈ {0, 1}) in ρ(G), with the edges between u i and v i having the same sign as e and the edges between u i and v 1-i having the opposite sign (i ∈ {0, 1}).

See Figure 1 for examples of signed graphs and their switching graphs. (In all our figures, dashed edges are red/negative, while full edges are blue/positive). The notion of switching graph was defined by Brewster and Graves in [START_REF] Brewster | Edge-switching homomorphisms of edge-coloured graphs[END_REF] in a more general setting related to permutations (they called it permutation graph). A related construction was used in [START_REF] Klostermeyer | Homomorphisms and oriented colorings of equivalence classes of oriented graphs[END_REF] in the context of digraphs. The construction is also used in [START_REF] Ochem | Homomorphisms of 2-edge-colored triangle-free planar graphs[END_REF] under the name antitwinned graph. Switching graphs play a key role in the study of signed graph homomorphisms, indeed they have several useful properties. One such property is that the switching graph of a signed graph contains, as subgraphs, all switching-equivalent signed graphs. Additionally, the following proposition allows us to study s-homomorphisms in the realm of standard homomorphisms.

Proposition 2.2 ([7]

). Let G and H be two signed graphs. Then,

G s -→ H if and only if G → ρ(H).
Thus, we obtain the following corollary.

Corollary 2.3. Let H be a signed graph. Then, s-Hom(H) and Planar s-Hom(H) have the same complexity as Hom(ρ(H)) and Planar Hom(ρ(H)), respectively.

The indicator construction

We recall the indicator construction, one of the main tools used in the proof of the Hell-Nešetřil dichotomy for Hom(H) in [START_REF] Hell | On the complexity of H-coloring[END_REF].

Definition 2.4. Let H be a signed graph. An indicator (I, i, j), is a signed graph I with two distinguished vertices i and j such that I admits an automorphism mapping i to j and vice-versa. The result of the indicator (I, i, j) applied to H is an undirected graph denoted H * and defined as follows.

(i) V (H * ) = V (H) (ii) There is an edge from u to v in H * if there is a homomorphism of I → H such that i → u and j → v.
We say that (I, i, j) preserves planarity if, given a planar undirected graph G, replacing each edge uv with a copy of (I, i, j) by identifying u with i and v with j, we obtain a planar signed graph.

The following result shows how we can use this tool.

Theorem 2.5 (Hell and Nešetřil [27]). Let H be a signed graph, (I, i, j), an indicator and H * , the undirected graph resulting from (I, i, j) applied to H. Then, Hom(H * ) admits a polynomial-time reduction to Hom(H).

Moreover, if the indicator construction preserves planarity, then Planar Hom(H * ) admits a polynomial-time reduction to Planar Hom(H).

Proof. We sketch the proof. Given an input graph G of Hom(H * ), we construct a signed graph f (G) by replacing each edge uv in G by a copy of (I, i, j) by identifying u with i and v with j. (If G is planar and (I, i, j) preserves planarity, then f (G) is also planar.) Now it is not difficult to show that G → H * if and only if f (G) → H.

As an example, consider the signed graph U C 4 and its switching graph ρ(U C 4 ). Let I be the 4-cycle with two parallel negative and two parallel positive edges, where i and j are two non-adjacent vertices i and j. The result ρ(U C 4 ) * of (I, i, j) applied to ρ(U C 4 ) is shown in Figure 1: it consists of two disjoint copies of K 4 (thus its core is K 4 ). By Theorem 2.5 and Corollary 2.3, this implies that Hom(ρ(U C 4 )) and s-Hom(U C 4 ) are NP-complete, by a reduction from Hom(K 4 ). Note that the application of (I, i, j) preserves planarity; however it is useless to reduce Planar Hom(K 4 ) to Planar Hom(U C 4 ) since the former is polynomial-time solvable by the Four Colour Theorem. We thus handle this case with an ad-hoc proof in Section 5.

U C 4 ρ(U C 4 ) i j (I, i, j) ρ(U C 4 ) *

Some NP-complete (non-signed) Planar Hom(H) cases

In this section, we prove that Planar Hom(H) is NP-complete for two special cases which were not known to be NP-complete.

Squares of cycles

We first deal with the case where H is the square C 2 t of a cycle C t . The proof is inspired by the proof that Planar Hom(C 2k+1 ) is NP-complete from [START_REF] Macgillivray | On the complexity of H-colouring planar graphs[END_REF]. Note that, C 2 4 = K 4 and C 2 5 = K 5 , and thus by the Four Colour Theorem Planar Hom(C 2 t ) is polynomial-time solvable when t = 4, 5.

Theorem 3.1. For every t 6, Planar Hom(C 2 t ) is NP-complete. Proof. We will reduce from Planar Hom(C 2k+1 ) for suitable values of k, which is NP-complete whenever k ≥ 1 [START_REF] Macgillivray | On the complexity of H-colouring planar graphs[END_REF]. The proof is split into different cases depending on the values of t mod 3 and t mod 4.

If t ≡ 0 mod 3, then the core of C 2 t is K 3 and we are done since Planar Hom(K 3 ) is NP-complete. Otherwise, C 2 t is a core. Let v 0 , . . . , v t-1 be its vertices and v i v i+1 and v i v i+2 be its edges (indices are taken modulo t).

If t ≡ 2 mod 4, then C 2 t is planar, the set of edges v i v i+1 induces a cycle of length t, and the set of edges v i v i+2 induces two disjoint odd cycles of length t/2. We reduce Planar Hom(C t/2 ) to Planar Hom(C 2 t ). Let G be a planar graph and let G ′ be the planar graph obtained from G as follows. For every edge e of G, we add a copy of C 2 t and we identify the edge v 0 v 2 of this copy of C ). Let G be a planar graph and let G ′ be the planar graph obtained from G as follows. For every edge e of G, we add a copy of H and we identify the edge v 0 v 1 of this copy of H with e. Again, G maps to C t if and only if G ′ maps to C 2 t and we are done. If t ≡ 0 mod 4, then both the set of edges v i v i+1 and the set of edges v i v i+2 induce a bipartite graph. Thus, the kind of reductions above does not work. We use instead a reduction similar to the one used for odd cycles in [START_REF] Macgillivray | On the complexity of H-colouring planar graphs[END_REF]. We reduce Planar Hom(K 3 ) (that is, Planar 3-Colouring) to Planar Hom(C 2 t ). Let us set t = 4k. Consider the graph H obtained from C 2 t by removing the edges v 2k-1 v 2k and v 2k v 2k+2 . Notice that every homomorphism of H to C 2 t that maps v 0 to v 0 also maps

v 2k to either v 2k-1 , v 2k , or v 2k+1 .
Let G be a planar graph and let G ′ be the planar graph obtained from a planar embedding of G as follows. For every face f of G, we first place a new vertex u f inside the face f , and then for every vertex w of G incident to f , we add a copy of H and identify v 0 with u f and v 2k with w. Every vertex in the subgraph G of G ′ is said to be old. If G is 3-colourable, then we can map the subgraph G of G ′ to the triangle v 2k-1 v 2k v 2k+1 of C 2 t . Then we can extend this C 2 t -colouring to G ′ such that every vertex u f of G ′ maps to v 0 .

It remains to show that if G ′ maps to C 2 t , then G is 3-colourable. So we suppose for contradiction that there exists a planar graph G such that G ′ maps to C 2 t and G is not 3-colourable. Moreover, we choose such a graph G with the minimum number of vertices.

Let us first show that G is a planar triangulation. Suppose to the contrary that G contains a face f of length at least 4. Then G ′ has a C 2 t -colouring that maps u f to v 0 . So, every old vertex in G ′ that corresponds to a vertex incident with f in G is mapped to a vertex in {v 2k-1 , v 2k , v 2k+1 }. Since |f | 4, two such old vertices x and y in G ′ get the same colour. Let H be the planar graph obtained from G by identifying x and y and removing multiple edges. Notice that H is not 3-colourable, whereas the graph H ′ obtained by applying our reduction to H maps to C 2 t . This contradicts the minimality of G and thus G is a planar triangulation.

Let w be any old vertex. Since G ′ maps to C 2 t , consider a C 2 t -colouring of G ′ that maps w to v 0 . Then every old vertex adjacent to w maps to a vertex in

S = {v -2 , v -1 , v 1 , v 2 }. Notice that S induces a path in C 2 t .
Since G is a triangulation, the old vertices adjacent to w induce a cycle C which maps to S. So C maps to a bipartite graph and thus C is bipartite. This means that the length of C is even and thus that the degree of w in G is even. Thus, the degree of every vertex of G is even, that is, G is an Eulerian planar triangulation. This is a contradiction since every Eulerian planar triangulation is 3-colourable (see Exercise 9.6.2 in [START_REF] Bondy | Graph Theory with Applications[END_REF]).

Cubic circular cliques

Recall that K 4t/(2t-1) is the circular clique with vertex set {k 0 , . . . , k 4t-1 } and such that k i is adjacent to k i+2t-1 , k i+2t , and k i+2t+1 (indices being taken modulo 4t). We now use our result of Section 3.1 to show the following. Theorem 3.2. For every t 2, Planar Hom(K 4t/(2t-1) ) is NP-complete.

Proof. We reduce Planar Hom(C 2 4t ), which is NP-complete by Theorem 3.1, to Planar Hom(K 4t/(2t-1) ). For this, consider the 1-edge-coloured indicator (C 2t+1 , i, j) consisting of a cycle of length 2t + 1 on which i and j are at distance 2. Clearly, this indicator construction preserves planarity. Now, consider a homomorphism f from (C 2t+1 , i, j) to K 4t/(2t-1) . By the symmetries of both graphs, we may assume that f (i) = k a for some a ∈ {0, . . . , 4k -1}. Note that the shortest odd cycles in K 4t/(2t-1) are of length 2t + 1. Thus, (C 2t+1 , i, j) must be mapped one-to-one. In fact, we must have f (j) ∈ {k a-2 , k a-1 , k a+1 , k a+2 } (where indices are taken modulo 4t). Thus, the graph K * 4t/(2t-1) obtained from applying (C 2t+1 , i, j) to K 4t/(2t-1) is isomorphic to C 2 4t , and by Theorem 2.5 the proof is complete.

Unbalanced even cycles of length at least 6

We are now ready to prove that unbalanced even cycles of length at least 6 define an NP-complete s-homomorphism problem for planar graphs. Proof. We will equivalently show that Planar Hom(ρ(U C 2k )) is NP-complete.

Let u 0 , . . . , u 4k-1 be the vertices of ρ(U C 2k ). The positive edges of ρ(U C 2k ) are u i u i+1 and the negative edges are u i u i+2k-1 .

Consider the indicator (I, i, j) of Figure 1. Clearly, it preserves planarity. Now, consider a homomorphism f of (I, i, j) to ρ(U C 2k ). By the symmetries of both graphs, we may assume that f (i) = u a for some a ∈ {0, . . . , 4k -1}. Then, we must have f (j) ∈ {u a+2k-2 , u a+2k , u a+2k+2 } (indices taken modulo 4k).

Thus, the graph ρ(U C 2k ) * obtained from applying (I, i, j) to ρ(U C 2k ) is cubic. Notice that ρ(U C 2k ) is bipartite, and that (I, i, j) is bipartite too with i and j in the same part. It follows that ρ(U C 2k ) * will consist of at least two connected components. See Figure 2 for a picture when k = 3, 4. We now distinguish two cases to determine ρ(U C 2k ) * .

Case 1: k is odd. In this case, ρ(U C 2k ) * contains a copy of the cycle C k = {c 0 , . . . , c k-1 }, where c 0 = u 0 and c i+1 = u i+2k+2 when i is even and c i+1 = u i-(2k-2) when i is odd (thus, c k = u 2k-2 ). Furthermore, we claim that C k is the core of ρ(U C 2k ) * : indeed, consider the k sets of vertices U j = {u j , . . . , u j+3 } for j = 0 mod 4 and 0 ≤ j < 4k. For

u i ∈ U j , let f (u i ) = c j : f is a homomorphism from ρ(U C 2k ) * to its subgraph C k .
Case 2: k is even. In this case, letting k = 2t with t ≥ 2, we have that ρ(U C 2k ) * consists of two copies of the circular clique K 4t/(2t-1) : one on vertex set {u i | i = 0 mod 2} and the other on vertex set {u i | i = 1 mod 2}. Thus, the core of ρ(U C 2k ) * is K 4t/(2t-1) .

In both cases, we have Planar Hom(ρ(U C 2k ) * ) NP-complete: by [START_REF] Hell | Complexity of planar homomorphisms[END_REF][START_REF] Macgillivray | On the complexity of H-colouring planar graphs[END_REF] when k is odd and by Theorem 3.2 when k is even. We thus apply Theorem 2.5 to obtain a reduction from Planar Hom(ρ(U C 2k ) * ) to Planar Hom(ρ(U C 2k )): this completes the proof.

Unbalanced cycles of length 4

The proof of Theorem 4.1 fails to show that Planar Hom(U C 4 ) is NP-complete since ρ(U C * 4 ) is K 4 and thus this would require Planar Hom(K 4 ) to be NP-complete, which is false by the Four Colour Theorem. However, we give an ad-hoc reduction in this section. construction of H, the important vertices belong to the same partite set. All of the vertices that will be named in our gadgets will always belong to that partite set. By the symmetry of ρ(U C 4 ), we can assume that, in every homomorphism from one of our graphs to ρ(U C 4 ), all of the named vertices will always be mapped to some u i with i = 0 mod 2.

For each vertex v of degree d in G, we will create a gadget G v in H with 2d special vertices v 0 , • • • v 2d-1 (called ports) such that there is an embedding of that gadget in the plane where v 0 , • • • v 2d-1 are on a facial trail in that order. We want that any homomorphism ϕ from H to ρ(U C 4 ) satisfies:

1. ϕ(v 0 ) = ϕ(v 1 ) 2. for i = 0, 1, ϕ(v i ) = ϕ(v (i mod 2) ).
We will describe later how to enforce these conditions. Assuming that they are satisfied, let ϕ be any homomorphism from H to ρ(U C 4 ). Let ϕ(v 1 ) = u l and ϕ(v 0 ) = u k . The difference l -k mod 8 will represent the colour of v in a valid 3-colouring of G. For the sake of readability, we identify u k with its index k, so that we can read the colour of v by the operation ϕ(v 1 ) -ϕ(v 0 ) mod 8. We shall call ϕ(v 0 ) the ground of v and ϕ(v 1 ) -ϕ(v 0 ) its colour. Note that Condition 1 ensures that there are only three possible colours for v: 2, 4, and 6. Condition 2 asserts that the colour of v propagates d times throughout the vertex gadget as ϕ(v 2i+1 ) -ϕ(v 2i ) mod 8, i ∈ {0, . . . , d -1}, allowing us to use any pair (v 2i , v 2i+1 ) for retrieving it.

Recall that we want H to be a positive instance of Planar Hom(ρ(U C 4 )) if and only if G is 3colourable. Therefore, we also want to ensure that any homomorphism H → ρ(U C 4 ) assigns different colours to each pair of adjacent vertices in G. We thus construct H such that the following condition is satisfied: 3. For each homomorphism ϕ : H → ρ(U C 4 ), two adjacent vertices in G receive the same ground, and different colours.

Note that if we manage to construct H such that the three conditions hold, then it is easy to recover a proper 3-colouring of G from any homomorphism H → ρ(U C 4 ). In the following subsections, we describe our gadgets, and we prove that the previous conditions hold.

Construction of the gadgets

Tu build our vertex gadget, we need to start with several smaller gadgets. We start with a first construction allowing to make copies of a vertex that are mapped to the same image under any homomorphism, called copy gadget (see Figure 4). Lemma 5.2. Let ϕ be a homomorphism from the copy gadget from Figure 4 to ρ(U C 4 ). Then, ϕ(x 1 ) = ϕ(x 2 ), ϕ(y 1 ) = ϕ(y 2 ) and ϕ(y 1 ) -ϕ(x 1 ) ∈ {±2}.

Conversely, if we partially fix ϕ from {x 1 , x 2 , y 1 , y 2 } to {u 0 , u 2 , u 4 , u 6 } such that ϕ(x 1 ) = ϕ(x 2 ), ϕ(y 1 ) = ϕ(y 2 ) and ϕ(y 1 ) -ϕ(x 1 ) ∈ {±2}, one can extend ϕ to a homomorphism from the copy gadget to ρ(U C 4 ). Proof. The first thing to notice is that in a homomorphism from a copy of U C 4 to ρ(U C 4 ), each vertex maps to a distinct vertex, and the only ways to do it are shown in Figure 5.

u i+1 u i+3 u i+2 u i u i+7 u i+5 u i+6 u i
Given the image of a vertex, there are two possibilities for the remainder of the copy of U C 4 , and given the images of two vertices, there is at most one way to complete the homomorphism. In a homomorphism from the gadget to ρ(U C 4 ), assume without loss of generality that x 1 maps to u 0 . The two possibilities to map the vertices of the copy of U C 4 containing x 1 lead to y 1 being mapped either to u 2 or u 6 . Then, the mapping of the remainder of the vertices is forced, leading to x 2 being mapped to u 0 and y 2 to the same vertex as y 1 . The symmetries of U C 4 complete the proof of the lemma.

Given a vertex v in G, we want to use the copy gadget to ensure that Condition 2 holds in the vertex gadget G v , by identifying x 1 with v 2i and x 2 with v 2i+2 for i = 0, . . . , d -1 (indices are taken modulo 2d). However, we also need to have a copy of the ground between each x i .

To this end, we have to design a crossing-type gadget. Observe that the copy gadget allows to cross two images as soon as they differ by ±2.

We thus need to find a gadget that can handle the case where the difference is 4. To this end, we introduce the split gadget from Figure 6, which allows to encode a difference of ±2 or ±4 using two differences of ±2. Lemma 5.3. Let ϕ be a homomorphism from the split gadget from Figure 6 to ρ(U C 4 ) such that ϕ(g 1 ) = ϕ(g 2 ) = ϕ(g 3 ).

x 1 x 2 y 2 g 1 g 2 g 3 g 1 x 1 x 2 g 2 y 2 g 3
Then, ϕ(x 2 ) -ϕ(g 2 ) and ϕ(y 2 ) -ϕ(g 3 ) lie in {±2}. Moreover, ϕ(x 1 ) -ϕ(g 1 ) = 4 if and only if ϕ(x 2 ) = ϕ(y 2 ), and ϕ(x 1 ) -ϕ(g 1 ) ∈ {±2} if and only if ϕ(x 2 ) = ϕ(y 2 ) = ϕ(x 1 ).

Conversely, if we partially fix ϕ from {x 2 , y 2 , x 1 , g 1 , g 2 , g 3 } to {u 0 , u 2 , u 4 , u 6 } such that ϕ(g 1 ) = ϕ(g 2 ) = ϕ(g 3 ), ϕ(x 2 ) -ϕ(g 2 ) and ϕ(y 2 ) -ϕ(g 3 ) lie in {±2}, ϕ(x 1 ) -ϕ(g 1 ) = 4 if and only if ϕ(x 2 ) = ϕ(y 2 ), and ϕ(x 1 ) -ϕ(g 1 ) ∈ {±2} if and only if ϕ(x 2 ) = ϕ(y 2 ) = ϕ(x 1 ), then one can extend ϕ to a homomorphism from the split gadget to ρ(U C 4 ).

Proof. Consider a homomorphism ϕ from the gadget to ρ(U C 4 ). Say that g 1 , g 2 , and g 3 are mapped to u 0 . Similarly to the proof of Lemma 5.2, x 2 and y 2 can each only be mapped to u 2 or u 6 . Furthermore, x 1 can only be mapped to u 2 , u 4 or u 6 . Now, if x 1 is mapped to u 4 , then its two neighbours in its copy of U C 4 are mapped one to u 3 and one to u 5 , forcing x 2 and y 2 to be mapped one to u 2 and the other to u 6 . If x 1 is mapped to u 2 , then its two neighbours in its copy of U C 4 are mapped one to u 1 and one to u 3 , forcing x 2 and y 2 to be mapped either both to u 2 or both to u 6 . The case when v 2i , v 2i+1 , w 2j with x 1 , y 1 , x 2 , and adding an alternating path of length 2 between y 2 and w 2j+1 as shown in Figure 9. Due to this construction, any homomorphism H → ρ(U C 4 ) must map the bottom vertex (x 2 ) from the crossing gadget and w 2j+1 to different images, with a difference in {±2, ±4}. Thus, Lemma 5.4 also ensures that Condition 3 holds since any homomorphism maps v 2i+1 and w 2j+1 to the same image (the ground) and v and w 2j to different ones (their colours).

x 1 is + + + . . . v 0 v 1 v 2 v d-2 v d-1 v d v d+1 v 2d-3 v 2d-2 v 2d-1 G v . . . v 0 v 1 v 2 v 2d-1
G v v 2i v 2i+1 + G w w 2j w 2j+1
To ensure that this construction outputs a planar graph H, we first fix a planar embedding of G. Then, we use the ports of the gadgets associated to v in the same cyclic ordering as the edges incident to v in G.

End of the proof

As we already saw, our three conditions are satisfied by H, hence if there is a homomorphism H → ρ(U C 4 ), then G is 3-colourable. Conversely, given a 3-colouring of G, we can define a homomorphism ϕ : H → ρ(U C 4 ). Given a vertex v of G with colour c ∈ {1, 2, 3}, we define ϕ(v 2i ) = u 0 and ϕ(v 2i+1 ) = u 2c . We can then extend this partial homomorphism to each crossing gadget. Therefore, we obtain a reduction. Since H can be constructed in polynomial time, we finally obtain that Planar Hom(ρ(U C 4 )) (and thus, Planar s-Hom(U C 4 )) is NP-hard.

Planar graphs with large girth

In this section, we prove a "hypothetical complexity" type theorem for s-homomorphisms to unbalanced even cycles, similar to the one in [START_REF] Esperet | A complexity dichotomy for the coloring of sparse graphs[END_REF] for Planar Hom(C 2k+1 ). This is motivated by the signed graph analogue of Jaeger's conjecture: it is conjectured in [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF] that every planar bipartite signed graph of girth at least 4k -2 has an s-homomorphism to U C 2k (see [START_REF] Charpentier | Homomorphisms of sparse signed graphs[END_REF] for recent progress). 2 be fixed integers. Either every bipartite planar signed graph with girth at least g has an s-homomorphism to U C 2k , or Planar s-Hom(U C 2k ) is NP-complete for planar signed graphs with girth at least g.

Proof. Note that by Proposition 2.2 and Corollary 2.3, the statement is equivalent to the one stating that every bipartite planar signed graph with girth at least g has a homomorphism to ρ(U C 2k ), or Planar Hom(ρ(U C 2k )) is NP-complete for planar signed graphs with girth at least g.

Suppose that H is a bipartite planar graph with girth at least that does not map to ρ(U C 2k ) and that H is minimal with respect to the subgraph order. Let xy be a positive edge of H. By minimality, H \ xy is ρ(U C 2k )-colourable. Let i be the smallest integer such that there exists a homomorphism that maps x to u 0 and y to u i . So i is odd and 3 i 2k -1. Let J be the graph obtained H \ xy by adding a path x = x 0 , x 1 , . . . , x i-1 , x i = y of i positive edges between x and y. So J is ρ(U C 2k )-colourable and since ρ(U C 2k ) is edge-transitive, we can assume that x 0 maps to u 0 and x 1 maps to u 1 . Then by minimality of i, x j maps to u j for every 0 j i and we call this a canonical colouring. Now we consider the graph J ′ obtained from two copies J 1 and J 2 of J by identifying the vertices x i-1 (resp. x i ) of both copies. If a canonical colouring of the subgraph J 1 is extended to J ′ , then both vertices x 0 map to u 0 . Thus, every ρ(U C 2k )-colouring of J ′ maps both vertices x 0 to the same vertex. Notice that the distance between the two vertices x 0 is 2i -2 4.

Then, every instance G of Planar Hom(ρ(U C 2k )) can be transformed into an equivalent instance G ′ of Planar Hom(ρ(U C 2k )) with girth at least g using, as a vertex gadget, sufficiently many copies of the gadget J ′ .

Restricting the maximum degree

We now consider instance restrictions according to the maximum degree. It is proved in [START_REF] Galluccio | The complexity of H-coloring of bounded degree graphs[END_REF] that Hom(C 2k+1 ) can be reduced to Hom(C 2k+1 ) for subcubic graphs using a gadget consisting of a sequence of copies of C 2k+1 glued to each other. Furthermore, this reduction preserves the planarity, thus it follows from [START_REF] Hell | Complexity of planar homomorphisms[END_REF][START_REF] Macgillivray | On the complexity of H-colouring planar graphs[END_REF] that Planar Hom(C 2k+1 ) is NP-complete for subcubic graphs. Here, we show an analogue of this result for s-homomorphisms to unbalanced even cycles. Proof. In both cases, we reduce Planar s-Hom(U C 2k ) itself to Planar s-Hom(U C 2k ) on graphs with maximum degree ∆ = 3 or 4 using a vertex-gadget with appropriate vertex degrees that forces the same colour (say colour 0) on arbitrarily many vertices of degree ∆ -1. Our gadgets are similar to the ones from [START_REF] Galluccio | The complexity of H-coloring of bounded degree graphs[END_REF] for Planar Hom(C 2k+1 ), and are depicted in Figure 10. For the reduction, each vertex v of degree d of the input graph is replaced by a copy G v of this gadget containing 2d glued cycles, and if v and w are adjacent, we add an edge between a vertex of G v and a vertex of G w that are labeled 0 in Figure 10. Since the gadgets have girth 2k and by Theorem 6.1, Planar s-Hom(U C 2k ) is NP-complete for inputs of girth 2k, our construction producees inputs of girth 2k.

Observe that this approach does not work for Planar s-Hom(U C 4 ) on subcubic graphs: vertices coloured with 0 in the corresponding gadget have degree 3, not 2.

Concluding remarks

It would be interesting to settle the complexities of s-Hom(U C 4 ) and Planar s-Hom(U C 4 ) for graphs of maximum degree 3. Studying Planar s-Hom(H) for further classes of signed graphs H is also of interest. As Planar Hom(H) is connected to studies on homomorphism bounds for planar graphs [START_REF] Hell | Complexity of planar homomorphisms[END_REF][START_REF] Naserasr | Homomorphisms and edge-coloring of planar graphs[END_REF][START_REF] Nešetřil | Tree-depth, subgraph colorings and homomorphism bounds[END_REF], Planar s-Hom(H) is connected to the signed counterparts of these works, see for example [START_REF] Beaudou | Homomorphism bounds of signed bipartite K 4 -minorfree graphs and edge-colourings of 2k-regular K 4 -minor-free multigraphs[END_REF][START_REF] Naserasr | Homomorphisms of planar signed graphs to signed projective cubes[END_REF]. When it comes to non-signed graphs, combined results of Moser [START_REF] Moser | The star-chromatic number of planar graphs[END_REF] and Zhu [START_REF] Zhu | Planar graphs with circular chromatic numbers between 3 and 4[END_REF] show that for every rational q such that 2 q 4, there exists a planar graph with circular chromatic number q. The problem of deciding whether the circular chromatic number of a planar graph is at most q is NP-complete if q is equal to:

• 3 + 1 2
, by Theorem 3.1 since C 2 7 = C 7 = K 7/2 .

• 2 + 1 t for every t 1 by [START_REF] Hell | Complexity of planar homomorphisms[END_REF][START_REF] Macgillivray | On the complexity of H-colouring planar graphs[END_REF] • 2 + 2 2t-1 for every t 2, by Theorem 3.2. It would be nice to extend these results to every rational q with 2 < q < 4.

Figure 1 :

 1 Figure 1: The unbalanced cycle U C 4 , its switching graph ρ(U C 4 ), the indicator (I, i, j) and its resulting undirected graph ρ(U C 4 ) * .

Theorem 4 . 1 .

 41 For every k 3, Planar s-Hom(U C 2k ) is NP-complete.

Theorem 5 . 1 .

 51 Planar s-Hom(U C 4 ) is NP-complete.

2 =Figure 4 :

 24 Figure 4: Copy gadget and its schematic representation.

Figure 5 :

 5 Figure 5: The only possible homomorphisms for a copy of U C 4 . The indices are taken modulo 8.

Figure 6 :

 6 Figure 6: Split gadget and its schematic representation.

Figure 8 :

 8 Figure 8: Vertex gadget Gv (dotted links mean identification of vertices) and its schematic representation.

Figure 9 :

 9 Figure 9: Edge gadget (dotted links mean identification vertices).

Theorem 6 . 1 .

 61 Let g 4 and k

Theorem 7 . 1 .

 71 Planar s-Hom(U C 4 ) remains NP-complete for signed graphs with maximum degree 4. For every k ≥ 3, Planar s-Hom(U C 2k ) remains NP-complete for subcubic signed graphs (of girth 2k).

  Duplicating a colour in a U C 4 -colouring. (b) Duplicating a colour in a U C 2k -colouring. A dotted edge corresponds to a path of 2k -4 positive edges.

Figure 10 :

 10 Figure 10: Gadgets with vertices of degree 3 or 2, that are mapped to the same vertex in a U C 2k -colouring.

  2 t with e. One can see that G maps to C t/2 if and only if G maps to C 2 t , and we are done. If t is odd, then C 2 t is not planar, the set of edges v i v i+1 (resp. v i v i+2 ) induces an odd cycle and there exists no automorphism of C 2 t that maps an edge v i v i+1 to an edge v i v i+2 . Consider the planar graph H obtained from C 2 t by removing the edge v 0 v 2 . Notice that every homomorphism of H to C 2

t actually corresponds to an automorphism of C 2 t . We reduce Planar Hom(C t ) to Planar Hom(C 2 t

This work is supported by the ANR project HOSIGRA (ANR-17-CE40-0022). 2 This author is partially supported by the IFCAM project "Applications of graph homomorphisms" (MA/IFCAM/18/39).

As before, we show equivalently that Planar Hom(ρ(U C 4 )) is NP-complete. It is easy to see that Planar Hom(ρ(U C 4 )) is in NP. We thus focus on proving NP-hardness. Recall that ρ(U C 4 ) is the circulant graph with vertices u 0 , . . . , u 7 , positive edges u i u i+1 and negative edges u i u i+3 (it is depicted in Figure 1, see also Figure 3 for a symmetric drawing). We reduce Planar Hom(K 3 ) (that is, Planar 3-Colouring), which is NP-complete [START_REF] Garey | Some simplified NP-Complete graph problems[END_REF], to Planar Hom(ρ(U C 4 )). In the following, G is an instance of Planar Hom(K 3 ). Our goal is to construct a planar signed graph H such that G is 3-colourable if and only if H is a positive instance of Planar Hom(ρ(U C 4 )). We assume that G is connected, otherwise, we apply our construction to each connected component.

Outline of the reduction

We first present the generic ideas of our reduction. Note that the graph ρ(U C 4 ) is bipartite. Therefore, H will be bipartite, otherwise there is no homomorphism from H to ρ(U C 4 ). In our mapped to u 6 is similar. If g 1 , g 2 , and g 3 are mapped to another u i , then the symmetries of ρ(U C 4 ) yield the result.

To prove the converse, one can check that every time we specified that something was forced above, there actually existed a homomorphism that verified the conditions.

Note that the split gadget can be used in two ways: for splitting an image in {±2, ±4} into two images in {±2}, but also "backwards" for combining two images in {±2} into an image in {±2, ±4}. Thus, by combining the copy gadget and the split gadget, we obtain our crossing gadget, that allows a crossing between two images that differ from ±2 or ±4, see Figure 7. It is clear that the result is planar. Notice that the six vertices towards the center (the lower vertices of the upper split gadget, the upper vertices of the lower split gadget, the right vertex of the left copy gadget, and the left vertex of the right copy gadget) are all identified into one vertex. Lemma 5.4. Let ϕ be a homomorphism from the crossing gadget depicted in Figure 7 to ρ(U C 4 ). Then, ϕ(x 1 ) = ϕ(x 2 ), ϕ(y 1 ) = ϕ(y 2 ) and ϕ(y 1 ) -ϕ(x 1 ) ∈ {±2, ±4}.

Conversely, if we partially fix ϕ from {x 1 , x 2 , y 1 , y 2 } to {u 0 , u 2 , u 4 , u 6 } such that ϕ(x 1 ) = ϕ(x 2 ), ϕ(y 1 ) = ϕ(y 2 ) and ϕ(y 1 ) -ϕ(x 1 ) ∈ {±2, ±4}, then one can extend ϕ to a homomorphism from the crossing gadget to ρ(U C 4 ).

Proof. The proof is a direct application of Lemmas 5.2 and 5.3. Consider a homomorphism from the gadget to ρ(U C 4 ). The vertices y 1 and y 2 be mapped to the same vertex due to the copy gadgets. Say y 1 and y 2 are mapped to u 0 . Notice that in addition, due to the copy gadgets and the identifications of vertices, all vertices of type g i from the two split gadgets are mapped to u 0 as well. Thus, Lemma 5.3 can be applied to the two split gadgets.

By Lemma 5.3, x 1 is mapped to u 2 , u 4 , or u 6 . If x 1 is mapped to u 2 or u 6 (say, u 2 ), then by Lemma 5.3, the remaining two labeled vertices (other than the g i 's) of the upper split gadget are also mapped to u 2 . So are their "copies" in the two copy gadgets, and by applying Lemma 5.3 to the lower split gadget, so is x 2 , as desired.

If x 1 is mapped to u 4 , then by Lemma 5.3 the remaining two vertices of the split gadget are mapped one to u 2 and one to u 6 ; thus, again, so are their copies in the copy gadgets, and thus again by Lemma 5.3 x 2 is mapped to u 4 .

The existence of a homomorphism extending any good mapping of x 1 , x 2 , y 1 , and y 2 to {u 0 , u 2 , u 4 , u 6 } can be checked similarly.

The whole vertex gadget is now created by gluing crossing gadgets, as shown in Figure 8. Due to Lemma 5.4, we obtain that Conditions 1 and 2 are satisfied.

We use again the crossing gadget to define the edge gadget. For each edge vw of G, we link two pairs (v 2i , v 2i+1 ) and (w 2j , w 2j+1 ) of consecutive ports of the vertex gadgets G v and G w by identifying


Deok-Hoon Jeong

Anezka Kvasnickova

Jean-Baptiste Boutin

David Cébron

Alban Sauret
email: asauret@ucsb.edu

Deposition of a particle-laden film on the inner wall of a tube

The withdrawal of a liquid or the translation of a liquid slug in a capillary tube leads to the deposition of a thin film on the inner wall. When particles or contaminants are present in the liquid, they deposit and contaminate the tube if the liquid film is sufficiently thick. In this article, we experimentally investigate the condition under which particles are deposited during the air invasion in a capillary tube initially filled with a dilute suspension. We show that the entrainment of particles in the film is controlled by the ratio of the particle and the tube radii and the capillary number associated with the front velocity. We also develop a model which suggests optimal operating conditions to avoid contamination during withdrawal of a suspension. This deposition mechanism can also be leveraged in coating processes by controlling the deposition of particles on the inner walls of channels.

I. INTRODUCTION

Multiphase flows involving liquid phases, gas, and solid particles are ubiquitous in the dispensing of liquid, coating of tubings, and flows in porous media [START_REF] Ingham | Transport phenomena in porous media[END_REF][START_REF] Blunt | Flow in porous media: pore-network models and multiphase flow[END_REF][START_REF] Koch | Inertial effects in suspension and porous-media flows[END_REF][START_REF] Schwarzkopf | Multiphase flows with droplets and particles[END_REF]. The presence of particles in porous media is especially important since it can lead to clogging events [START_REF] Dressaire | Clogging of microfluidic systems[END_REF]. The liquid initially filling the tube or the pores is commonly displaced by a non-miscible fluid, e.g., air [START_REF] Maxworthy | Experimental study of interface instability in a hele-shaw cell[END_REF][START_REF] Strait | Two fluid flow in a capillary tube[END_REF]. As an invading fluid pushes the other fluid forward in a tube, this latter leaves behind a thin liquid layer or a series of drops depending on fluid properties and velocity [START_REF] Aussillous | Quick deposition of a fluid on the wall of a tube[END_REF][START_REF] Magniez | Dynamics of liquid plugs in prewetted capillary tubes: from acceleration and rupture to deceleration and airway obstruction[END_REF][START_REF] Zhao | Forced wetting transition and bubble pinch-off in a capillary tube[END_REF][START_REF] Hayoun | Film thickness selection for partially wetting, low-viscosity liquids challenges the standard model of triple line dynamics[END_REF]. The situation of a slug of wetting liquid pushed by an immiscible fluid has been considered in various studies, because of its relevance in liquid dispensing and coating of tubing [START_REF] Aussillous | Quick deposition of a fluid on the wall of a tube[END_REF][START_REF] Taylor | Deposition of a viscous fluid on the wall of a tube[END_REF][START_REF] Reinelt | The penetration of a finger into a viscous fluid in a channel and tube[END_REF][START_REF] Giavedoni | The axisymmetric and plane cases of a gas phase steadily displacing a newtonian liquid-a simultaneous solution of the governing equations[END_REF]. When the gravitational and inertial forces are negligible, the thickness of the liquid film h 0 deposited on the inner wall of a capillary of radius R by a Newtonian fluid of dynamic viscosity µ and surface tension γ for a front velocity U is governed by the competition between viscous and surface tension forces, captured through the capillary number Ca = µ U/γ [see, e.g., [START_REF] Aussillous | Quick deposition of a fluid on the wall of a tube[END_REF][START_REF] Balestra | Viscous taylor droplets in axisymmetric and planar tubes: from bretherton's theory to empirical models[END_REF]. The film thickness h 0 in a capillary tube has initially been predicted by Bretherton in the limit Ca 1: h 0 /R = 1.34Ca 2/3 [START_REF] Bretherton | The motion of long bubbles in tubes[END_REF]. The evolution of the film thickness for a broader range of parameters has been obtained through experiments and simulations [see, e.g. , 15]. In particular, the thickness of the film resulting from air invasion in a capillary filled with a Newtonian liquid is captured by the empirical relation [START_REF] Aussillous | Quick deposition of a fluid on the wall of a tube[END_REF]:

h 0 R = 1.34Ca 2/3 1 + 3.35 Ca 2/3 . (1)
Different extensions of this model have considered curved [START_REF] Muradoglu | Motion of large bubbles in curved channels[END_REF] and non-cylindrical channels [START_REF] Andrew | The steady propagation of a semi-infinite bubble into a tube of elliptical or rectangular cross-section[END_REF]. For a partially wetting fluid, the contact line motion also plays a role in determining the deposition patterns [START_REF] Zhao | Forced wetting transition and bubble pinch-off in a capillary tube[END_REF][START_REF] Cueto-Felgueroso | Macroscopic phase-field model of partial wetting: bubbles in a capillary tube[END_REF]. Most past studies have considered one fluid pushed by a second immiscible fluid.

The influence of particles on the deposition and the composition of the thin film coating the inner wall of the capillary remains elusive. This configuration is nevertheless relevant to model the flow of suspensions in porous media and contamination of tubings. A description of the thin film formation is required to account for the influence of the particles dispersed in the liquid. However, because the film thickness and the diameter of the particles can be of the same order of magnitude, the particles deform the air/liquid interface and may modify the interfacial dynamics. Previous works with particulate suspensions have shown that fluid-fluid interfaces can reduce the length scale of the flow to less than a few particle diameters [START_REF] Bonnoit | Mesoscopic length scale controls the rheology of dense suspensions[END_REF]. This situation occurs between two fluid-fluid interfaces, for instance, during the pinch-off of suspension, which is strongly modified by the presence of particles [START_REF] Furbank | An experimental study of particle effects on drop formation[END_REF][START_REF] Bonnoit | Accelerated drop detachment in granular suspensions[END_REF][START_REF] Château | Pinch-off of a viscous suspension thread[END_REF], and during the spreading and fragmentation of suspension sheets [START_REF] Pascal S Raux | Spreading and fragmentation of particle-laden liquid sheets[END_REF]. When extruding a suspension from a nozzle, the ligament of liquid thins out and eventually pinches off to generate a droplet due to interfacial effects. In tubings and porous media, the situation becomes even more complex because of the presence of solid surfaces. This type of particle confinement is at play during the drainage of suspension films [START_REF] Buchanan | Pattern Formation in Draining Thin Film Suspensions[END_REF], impact of a suspension drop on a substrate [START_REF] Lubbers | Dense suspension splat: Monolayer spreading and hole formation after impact[END_REF][START_REF] Grishaev | Impact of particle-laden drops: Particle distribution on the substrate[END_REF], the dip coating of suspensions [START_REF] Xu | Particle-induced viscous fingering[END_REF][START_REF] Kim | Formation and destabilization of the particle band on the fluid-fluid interface[END_REF][START_REF] Luo | Particle-induced viscous fingering: Review and outlook[END_REF][START_REF] Xu | The enhancement of viscous fingering with bidisperse particle suspension[END_REF][START_REF] Kudrolli | Unstable invasion of sedimenting granular suspensions[END_REF], viscous fingering [START_REF] Xu | Particle-induced viscous fingering[END_REF][START_REF] Kim | Formation and destabilization of the particle band on the fluid-fluid interface[END_REF], and bubble rise in confined suspensions [START_REF] Madec | Puzzling bubble rise speed increase in dense granular suspensions[END_REF]. The displacement of the particles is controlled by the capillary force, the drag force exerted by the fluid, and the friction on the solid substrate. The complexity of such a situation was recently considered by Yu et al. [START_REF] Yu | Armoring confined bubbles in the flow of colloidal suspensions[END_REF], who investigated the coating of the air/liquid interface of a long gas bubble translating in a mixture of glycerol and particles exhibiting a finite contact angle. Yu et al. also reported the possible separation of a bidisperse suspension by size using the motion of a confined bubble [START_REF] Yu | Separation of particles by size from a suspension using the motion of a confined bubble[END_REF]. The influence of the coupling between particles and interfacial dynamics has also recently been considered in the dip coating configuration, where a substrate is withdrawn from a particulate suspension [START_REF] Gans | Dip-coating of suspensions[END_REF][START_REF] Palma | Dip-coating with a particulate suspension[END_REF]. In this situation, it has been shown that particles dispersed in a wetting fluid are entrained in the coating film when the thickness at the stagnation point is larger than a certain fraction of the particle diameter [START_REF] Colosqui | Hydrodynamically Driven Colloidal Assembly in Dip Coating[END_REF][START_REF] Sauret | Capillary filtering of particles during dip coating[END_REF][START_REF] Dincau | Capillary sorting of particles by dip coating[END_REF][START_REF] Dincau | Entrainment of particles during the withdrawal of a fibre from a dilute suspension[END_REF]. These experiments have shown that particles up to six times larger than the liquid film can contaminate the withdrawn surface [START_REF] Sauret | Capillary filtering of particles during dip coating[END_REF]. Besides, this criterion was also found to be observed with biological microorganisms. The flow topology associated with the dip-coating configuration shares common features with the flow of a slug of liquid in a tube and the withdrawal of a liquid from a circular capillary. In particular, both configurations involve the presence of a stagnation point that governs the thickness of the coating film. Therefore, a similar condition for particle entrainment based on the particle size and the film thickness at the stagnation can be expected. To the best of our knowledge, no accurate determination of this threshold, which controls the possible entrainment of particles in a coating film on the wall of a capillary tube, has been obtained.

In this article, we report the deposition of particles during the invasion of air in a capillary tube initially filled with a dilute suspension. We predict the entrainment threshold of particles in the film and show that this situation shares common features with the dip-coating configuration, suggesting that particle entrainment is universal in the formation of thin-films governed by a stagnation point.

II. EXPERIMENTAL METHODS

In our experiments, we initially fill a cylindrical glass capillary tube open to the atmosphere on the other side. The dilute suspension of non-Brownian particles is then withdrawn at a constant velocity U , leaving a liquid film of thickness h 0 on the inner wall of the tube [Fig. 1(a)]. The experiments are performed in capillary tubes (borosilicate glass from Vitrocom) of inner radii R = [500, 750, 1000] µm placed vertically. Between experiments, the capillary tubes were thoroughly cleaned with Isopropanol (IPA), acetone, and DI water and properly dried with an air gun. The suspension consists of spherical polystyrene (PS) particles (Dynoseeds TS from Microbeads) dispersed in silicone oil (µ = 0.12 Pa.s, γ 22 ± 2 mN.m -1 ), which perfectly wets the capillary tube and the particles. We used three different particle sizes and measured the size distribution of each batch through image analysis. The different particle radii used in this study are a = 40 ± 3.5 µm, a = 72 ± 4 µm and a = 125 ± 3 µm. The density of the particles was measured by mixing them with a mixture of DI water and Sodium Chloride (NaCl) until we reach a close density match. For the particles used here, the density is found to be ρ P = 1056 ± 2kgm -3 . The dilute suspensions are prepared using a precision scale (Ohaus, PX series), and the particles are dispersed in the silicone oil using a mechanical stirrer (Badger Air-Brush Paint Mixer). The density matching between the particles and the liquid allows us to consider that the particles are neutrally buoyant over the timescale of an experiment. Small volume fractions are considered, 0.32% < φ < 1%, so that collective effects between particles can be neglected, and the viscosity is not significantly modified [START_REF] Boyer | Unifying suspension and granular rheology[END_REF][START_REF] Guazzelli | Rheology of dense granular suspensions[END_REF]. The Reynolds number is small Re 1, and inertial effects can be neglected. We connect one end of the capillary tube to a syringe filled with the dilute suspension. The other end of the capillary tube is open to the atmosphere. The suspension is first injected in the capillary and then withdrawn at a constant flow rate Q using a syringe pump. Withdrawing the suspension, instead of injecting compressible air, allows us to reach a constant velocity of the air-liquid front quickly. The velocity of the air-liquid interface U is directly related to the withdrawal flow rate through the relation U = Q/ π R 2 and is also measured by image processing using ImageJ. To visualize the motion of the suspension, the air-liquid meniscus, and the particles deposited on the wall of the capillary, we use a backlight LED Panel (Phlox). The motion and the final morphology of the coating film are recorded with a DSLR camera (Nikon D5300) and, when needed, with a highspeed camera (Phantom VEO 710L) equipped with a macro-lens (Nikkor 200mm) and microscopic lens (Mitutoyo). The curved surface of the cylindrical glass capillary tube leads to optical distortion, and does not allow clear visualization of the liquid film and of the particles deposited on the inner wall. Therefore, we inserted the cylindrical capillary tube in a square capillary, and injected glycerol between the capillaries as its refractive index matches the index of the borosilicate glass. This method ensured that the optical distortions due to the curved walls of the inner capillary are avoided [START_REF] Zhao | Forced wetting transition and bubble pinch-off in a capillary tube[END_REF]. The threshold velocity for particle entrainment in the coating film is determined as the average of the largest value of the air/liquid front velocity where no isolated particles are visible in the film and the smaller value of the air/liquid front velocity where individual particles are entrained.

An example of the experiment is shown in Fig. 1(b), where air invades the capillary tube in the presence of particles. We observe that (i) the particle reaches the meniscus, (ii) deforms the liquid/air interface, and (iii) is entrained in the coating film whereas its diameter is larger than the film thickness. After being deposited, the particle strongly deforms the film and does not move anymore, coating the inner wall of the tube. This example shows that particle of diameter larger than the film thickness can be entrained contrary to the situation of two rigid boundaries where sieving effects would occur [START_REF] Dressaire | Clogging of microfluidic systems[END_REF][START_REF] Sauret | Clogging by sieving in microchannels: Application to the detection of contaminants in colloidal suspensions[END_REF][START_REF] Sauret | Growth of clogs in parallel microchannels[END_REF].

III. RESULTS

A. Coating of Newtonian fluids

We first performed the experiments without particles for two silicone oils of different viscosities in a capillary tube of radius R = 750 µm. The experimental data, reported in figure 2, are captured by the Taylor's law [Eq. ( 1)] in the entire range of capillary numbers considered here [START_REF] Aussillous | Quick deposition of a fluid on the wall of a tube[END_REF][START_REF] Balestra | Viscous taylor droplets in axisymmetric and planar tubes: from bretherton's theory to empirical models[END_REF]. Besides, the prediction given by h 0 /R = 1.34Ca 2/3 , valid in the limit of small capillary numbers Ca = µ U/γ 1, agrees with the Taylor's law, within around 10%, for Ca 10 -2 . We shall see later that for the experimental parameters considered here the entrainment of particles dispersed in the liquid occurs for capillary numbers Ca 10 -2 , thus the Bretherton's law, h 0 /R = 1.34Ca 2/3 , is expected to give a good prediction and will be used in the following.

B. Deposition threshold of particles in the coating film

The no-deposition and deposition regimes are illustrated in Fig. 3(a). At low front velocity U , no particles are visible in the film. Particles start to be entrained in the film beyond a threshold velocity U * . The particles are randomly dispersed, and the number of particles per surface area increases with the velocity. The threshold velocity U * depends both on the radius of the particles a and the radius of the tube R [Fig. 3(b)]. The situation observed here is reminiscent of the results

1 0 FIG. 2.
Rescaled thickness h0/R of the coated film on the wall of the capillary tube when varying the capillary number Ca for µ = 0.12 Pa.s (blue symbols) and µ = 0.24 Pa.s (red symbols). The dashed line and the solid line represent the theoretical expression h0/R = 1.34Ca 2/3 and the empirical Taylor's law given by Eq. ( 1), respectively. reported for dip coating [START_REF] Sauret | Capillary filtering of particles during dip coating[END_REF]. Besides, for every configuration considered here, particles are able to squeeze into films thinner than the particle diameter.

Examples of the time-evolution of the position of a particle are reported in Fig. 4(a) and 4(b) for the no-deposition and deposition regimes, respectively. When a particle is not entrained in the film, it first approaches the interface before recirculating in the bulk [inset of Fig. 4(a)]. In this regime, all particles follow similar dynamics. The entrainment case exhibits different dynamics, as illustrated in Fig. 4(b). The particle first approaches the interface in a similar way, but the velocity of the particle remains smaller than the front velocity. The particle is then entrained in the coating film where it reaches a zero velocity in the frame of reference of the laboratory, i.e., and the particle Once deposited on the tube inner wall, the particle is trapped between the wall and the air/liquid interface so that it does not move anymore and remains deposited. These two distinct behaviors suggest that the presence of a stagnation point on the air/liquid front is a key parameter. Indeed, the streamlines ending at this location separate the region where the fluid flows into the film and a recirculation region within the bulk. Therefore, we expect that the thickness h * at the stagnation point is the relevant parameter that controls the entrainment of particles in the film [START_REF] Colosqui | Hydrodynamically Driven Colloidal Assembly in Dip Coating[END_REF][START_REF] Sauret | Capillary filtering of particles during dip coating[END_REF].

IV. DISCUSSION

A. Theoretical thickness at the stagnation point

We consider the air invasion in a cylindrical tube in the limit Ca 1 leading to the deposition of a film of uniform thickness h 0 on the wall. The thickness h 0 also corresponds to the thickness observed far from the front and rear menisci during the translation of a long bubble [START_REF] Bretherton | The motion of long bubbles in tubes[END_REF]. In this limit, the lengthscale , associated with the meniscus, and h 0 , associated with the liquid film thickness far from the meniscus, satisfy h 0 / = Ca 1/3 1 and |dh/dx| 1 [START_REF] Bretherton | The motion of long bubbles in tubes[END_REF]. Besides, h R, so that locally the situation is 2D and we use the cartesian coordinates system (x, y), where x is along the capillary and y is oriented inward. The interface is given by h(x, t), and the front is translating at the velocity U = U e x . The Reynolds number remains small and we use the Stokes' equations in the lubrication analysis:

u x + v y = 0 (2a) 0 = -p x + µ u yy (2b) 0 = -p y (2c)
On the wall of the capillary tube, the velocity field satisfies no-slip boundary conditions, so that in the reference frame moving with the air/liquid front u(x, 0, t) = -U and v(x, 0, t) = 0. The boundary conditions at the free surface at the leading order in Ca are ∂u/∂y| y=h = 0 and p = -γ κ, where κ = ∂ xx h + 1/R ∂ xx h. Equation 2(c) shows that the pressure field is only a function of x. Integrating equation 2(b) twice with respect to y, and using the boundary conditions leads to:

u(x, y) = - γ µ ∂ xxx h y 2 2 -h y -U, (3)
To simplify this expression, we consider the classical lubrication equation [see e.g., 46]

h t + γ 3µ ∂ x h 3 ∂ xxx h = 0. (4)
In the reference frame moving with the front at the velocity U , the solution is of the form h(x, t) = h(x -U t). The previous equation can be integrated with respect to x together with the boundary conditions h(x → -∞) = h 0 and ∂ xxx h(x → -∞) = 0 so that

h 2 ∂ xxx h = 3 µ U γ 1 - h 0 h , (5)
which corresponds to the canonical Landau-Levich-Derjaguin-Bretherton equation. The velocity of the interface is obtained using Eq. ( 3) and Eq. ( 5) and by setting y = h(x):

u s (x) = u(x, y = h) = U 3 2 1 - h 0 h -1 . (6)
The surface velocity changes sign along the interface at least once since far from the meniscus, i.e., x → -∞, h(x) = h 0 so that u s = -U < 0, and for x = 0, i.e., at the meniscus, h 0 /h ∼ 0 so that u s = U/2 > 0. The thickness at the stagnation point h * corresponds to the point where the surface velocity vanishes, leading to

h * = C h 0 , where C = 3. ( 7
)
This result is similar to the dip coating of a plate [START_REF] Sauret | Capillary filtering of particles during dip coating[END_REF] and a fiber [START_REF] Dincau | Entrainment of particles during the withdrawal of a fibre from a dilute suspension[END_REF]. Note that this analytical results applies, a priori, only when the Bretherton law is valid, i.e., Ca 1 and h R.

B. Numerical simulation

We performed numerical simulations of the fluid flow to characterize the prefactor C in the range of Ca, where particles are experimentally entrained. The model relies on the method developed by Balestra et al. [START_REF] Balestra | Viscous taylor droplets in axisymmetric and planar tubes: from bretherton's theory to empirical models[END_REF] and uses a laminar two phase-flow approach with moving mesh, where the fluidfluid interface is resolved in each step by an Arbitrary Lagrangian-Eulerian (ALE) method. The initial velocity of the outer liquid is imposed as U ∞ . U d then denotes the average velocity on the surface of the droplet. The capillary number associated with the droplet is given by Ca = U d µ/γ, where γ is the surface tension at the interface of the droplet and µ is the viscosity of the surrounding liquid. The ratio between the inner and outer viscosity, λ = µ in /µ, was fixed at 0.01 since it has been shown that this value of λ gives the same flow profile and film thickness as those obtained at smaller values of λ [START_REF] Balestra | Viscous taylor droplets in axisymmetric and planar tubes: from bretherton's theory to empirical models[END_REF]. The ratio of densities does not affect the results and is thus set to 1. The model converges to a stationary solution when the droplet reaches its equilibrium shape and moves with a steady velocity U d . The moving mesh helps to avoid large deformations of the mesh associated with the moving droplet. Furthermore, the problem is solved in the moving frame of reference attached to the droplet, the droplet hence practically does not change its position. The inlet in the model is imposed as a laminar Poiseuille flow, with mean velocity U ∞ -U d . The velocity at the walls is imposed as -U d , and the velocity of the bubble is determined and recalculated at each time step. We benchmarked the code by ensuring that the numerical simulation recovered the experimental results of Aussillous & Quéré for Ca ≤ 10 -1 [START_REF] Aussillous | Quick deposition of a fluid on the wall of a tube[END_REF]. More details on the numerical procedure can be found in Ref. [START_REF] Balestra | Viscous taylor droplets in axisymmetric and planar tubes: from bretherton's theory to empirical models[END_REF]. Examples of streamlines observed numerically are shown in Fig. 5(a) for various capillary numbers. The numerical results report that the main features of the flow remain similar, but the thickness of the liquid film on the wall of the capillary increases when increasing the capillary number. Fig. 5(b) shows a zoom in the region surrounding the stagnation point S * that delimitates the region where the fluid flows into the film and a recirculation region within the bulk.

We measure the thickness h 0 in the uniform film region. The stagnation point corresponds to the location at the interface where the surface velocity vanishes allowing us to measure h * . The dimensionless thicknesses h 0 /R and h * /R are reported in Fig. 6. The simulations agree with the theoretical expression [START_REF] Strait | Two fluid flow in a capillary tube[END_REF]. Furthermore, the numerical results demonstrate that the coefficient C = 3 obtained analytically can also be used with the Taylor's law given by Eq. ( 1) for a better prediction of h * for Ca ∼ 10 -2 so that:

h * R = 4.02 Ca 2/3 1 + 3.35 Ca 2/3 . (8)
C. Entrainment threshold Fig. 7(a) reports that the threshold capillary number Ca * for particle entrainment increases with (a/R) 2 . The larger the particle is, the larger the coating film must be, and thus the associated capillary number, to entrain the particle. A particle is entrained if the thickness at the stagnation point is larger than a fraction of the particle diameter 2a leading to the condition h * ≥ α a, where 1 ≤ α ≤ 2. The particle can be entrained only if it follows the streamlines entering the coating film, corresponding to the condition α min = 1. Besides, if the particle does not deform the air/liquid interface, no capillary force is exerted on the particle, which will always be entrained in the film, so that an upper bound is α max = 2. Assuming that an isolated particle does not significantly modify the flow topology and using Eq. ( 8), we obtain the capillary threshold value for particle entrainment:

Ca * = α 4.02 3/2 a R 3/2 . ( 9
) 0 0 FIG. 6.
Evolution of h0/R and h * /R with Ca. The squares are the numerical results, the solid red line is h0/R = 1.34Ca 2/3 , and the solid blue line corresponds to h * /R = 3 h0/R. The red dashed line is given by Eq. ( 1), and the blue dashed line by Eq. ( 8). a thin fiber [START_REF] Dincau | Entrainment of particles during the withdrawal of a fibre from a dilute suspension[END_REF] and the present experiments. In both figures the solid line is Eq. ( 9) with α = 1.15. (b) Thickness at the stagnation point calculated theoretically (knowing the experimental parameters) allowing a particle to be entrained in the coating film as a function of the radius of the particle a. The dashed line shows the linear law: h * th = a. Inset: Entrainement of a 125 µm particle in the coating film (Ca = 6.1 ×10 -2 ) illustrating that an entrained particle can be smaller than the liquid film thickness owing to the deformation of the air/liquid interface. The scale bar is 200 µm. Fig. 7(a) shows that all the experiments performed collapse on a master curve given by Eq. ( 9), where α = 1.15 ± 0.1. The coupling of the liquid/air interface and the particle is complex. However, we can provide some rationalization of the value of α by considering the force acting on the particle near the stagnation point that controls its entrainment into the coating film.

D. Force acting on the particle near the stagnation point

The entrainment of the particle is initially controlled by the passive advection of the particle that follows the streamlines. Once the particle approaches the stagnation point, the experimental observations show that the particle strongly deforms the air/liquid interface. The particle is assumed to be in contact with the substrate, owing to its surface roughness of order 100 nm [START_REF] Lubbers | Dense suspension splat: Monolayer spreading and hole formation after impact[END_REF][START_REF] Deboeuf | Particle pressure in a sheared suspension: A bridge from osmosis to granular dilatancy[END_REF]. Therefore, the entrainment of a particle is governed by the competition between the interfacial force, the viscous drag, and the friction on the substrate. The three phases situation (particle, air, liquid) leads to a complex interplay, and we try here to estimate the forces acting on the particle. The experimental results show that the entrainment threshold occurs for a thickness at the stagnation point h * of the same order as the particle radius a [Fig. 7(b)]. Therefore, we consider the force acting on a particle of radius a located at the stagnation point of thickness h * ∼ a. We further assume that far from the particle, the interface has a shape similar to the situation without particle.

A schematic of a particle fully wetted by a liquid of thickness h * around the stagnation point is shown in Fig. 8. Below, we detail the amplitude and orientation of the different forces to estimate their influence on particle entrainment. We consider the situation in the frame of reference moving with the front. Besides, close to the entrainment threshold, the velocity of the particle nearly vanished at the stagnation point before being able to be entrained in the coating film. The experimental parameters imposed that inertial effects are negligible since Re

1. An estimate of the viscous drag acting on the particle can be obtained by considering the average viscous stress acting on the particle: µ U/(2 h * ) [START_REF] Lubbers | Dense suspension splat: Monolayer spreading and hole formation after impact[END_REF]. Furthermore, the viscous stress acts over half of the particle since h * ∼ a so that the total drag is of order

F D ∼ µ U 2 h * π a 2 2 ∼ µ π U a 4 . (10)
The drag force acts along the x-axis and acts as a driving force to entrain the particle (see Fig. 8).

Since the particle is totally wetted by the liquid (contact angle: θ = 0), the capillary force is acting downard, pushing the particle against the wall of the capillary tube. The amplitude of the capillary force is given by (see, e.g., [START_REF] Gómez-Suárez | Analysis of bacterial detachment from substratum surfaces by the passage of air-liquid interfaces[END_REF]):

F γ = 2 π a γ sin φ sin(θ -φ), ( 11
)
where a is the radius of the particle, γ the interfacial tension, φ the filling angle and here θ = 0 since the silicone oil perfectly wets the particle. For a liquid film of thickness h ∼ a, the absolute value of the amplitude of the capillary force reduced to F γ = 2 π a γ sin 2 φ. The capillary force is maximum for φ = π/2, corresponding to h ∼ a, so that an order of magnitude of the capillary force acting on the particle is

F γ ∼ 2 π a γ (12)
As illustrated in Fig. 8 the capillary force can be decomposed in its y component that pushes the particle toward the surface of the capillary tube

F γ | y ∼ -2 π a γ cos β (13)
and an axial force acting to keep the particle in the liquid reservoir (in the direction of the front):

F γ | x ∼ 2 π a γ sin β (14)
The angle β comes from the inclination of the air/liquid interface between the front and the region of uniform coating thickness. Note that we have neglected the radial curvature of the capillary since both h * and a are very small compared to R. The slope at the interface close to the stagnation point is obtained by linearizing the Landau-Levich-Derjaguin-Bretherton (LLDB) equation for the thickness [START_REF] Colosqui | Hydrodynamically Driven Colloidal Assembly in Dip Coating[END_REF][START_REF] Landau | Dragging of a liquid by a moving plate[END_REF]:

h(x) = h 0 + (h * -h 0 ) exp - (x -x * ) h 0 /(3 Ca 1/3 ) , (15)
As a result, an approximate solution of the slope is tan β = dh(x * )/dx ∼ -3 Ca 1/3 . In the range of parameters considered here leading to the entrainment of the particles Ca ∼ 10 -3 -10 -2 , so that

β ∼ 15 o -35 o .
The resistance of the particle motion when the front is advancing and trapping of the particle at the stagnation point occurs because the particle becomes in physical contact with the glass substrate [START_REF] Lubbers | Dense suspension splat: Monolayer spreading and hole formation after impact[END_REF]. The particle is thus subject to a dynamic friction F T = µ d F N , where µ d 0.3 is an estimate of the dynamic friction coefficient between the immersed polystyrene particle and the glass substrate [START_REF] Tapia | Influence of surface roughness on the rheology of immersed and dry frictional spheres[END_REF] and F N denotes the normal force confining the particle against the substrate, i.e. the y component of the capillary force given by Eq. [START_REF] Reinelt | The penetration of a finger into a viscous fluid in a channel and tube[END_REF]. Therefore, the dynamic friction force, oriented along x < 0 and opposed to the motion of the front, is

F T ∼ 2 µ d π a γ cos β (16)
We can now estimate the order of the magnitude of the two opposite forces induced by the deformation of the interface by the particles. The x-component of the capillary force tends to keep the particle within the bulk liquid, whereas the y-component confine the particle and leads to the friction force that favors the particle entrainment during the translation of the air/liquid front. Using Eqs. ( 14) and ( 16) together with the expression of β, leads to an order of magnitude of the ratio of these forces:

F γ | x F T = tan β µ d ∼ 3 Ca 1/3 µ d , (17)
For the order of magnitude of capillary number leading to capillary entrainment in this study, Ca ∼ 10 -3 -10 -2 , we found that this ratio is of order unity (between 0.8 and 1.85). Therefore, the effects of the capillary force induced by the deformation of the interface mostly balance each other.

Using the order of magnitude of the experimental parameters used in this study, we can estimate the drag force and the friction force that also contribute to entrain the particle in the coating film and the capillary force along x that prevents the deposition of the particle in the coating film. An order of magnitude of the ratio of these two opposite effects is given by

F D + F T F γ | x ∼ Ca 8 + µ d 3 Ca 1/3 ∼ µ d 3 Ca 1/3 . (18)
The two components of the capillary forces mainly balance each other owing to the friction force induced by the contact of the particle on the wall. The main limitation to entrain the particle in the film is thus the possibility for a particle to follow the streamlines leading to the coating flow, corresponding to the condition α ∼ 1 as observed experimentally.

The value of α is also in quantitative agreement with previous experiments on dip-coating of plates and thin fibers [START_REF] Sauret | Capillary filtering of particles during dip coating[END_REF][START_REF] Dincau | Entrainment of particles during the withdrawal of a fibre from a dilute suspension[END_REF] as reported in the inset of Fig. 7 (note that the because of the flat geometry, the relevant parameter for the plate configuration is (2 a/ c ) 2 to account for the difference in geometry). Therefore, the entrainment of particles in a coating film governed by a stagnation point is controlled by a universal mechanism for dip coating, coating of the inner wall of a tube, and is expected to hold for a confined air bubble in a perfectly wetting fluid. The translation of a long bubble beyond the entrainment threshold would lead to similar results, except that particles will first be trapped in the liquid film and then released in the liquid at the rear of the bubble. In particular, contrary to the recent experiments of Yu et al. [START_REF] Yingxian | Time-dependent motion of a confined bubble in a tube: transition between two steady states[END_REF], no attachment of particles at the air/water interface of the bubble would be observed because the liquid fully wets the particles.

We should emphasize that we have considered diluted suspension in this work so that particles can be considered as isolated [START_REF] Sauret | Capillary filtering of particles during dip coating[END_REF]. For larger volume fractions of the suspension, the entrainment of clusters may be observed as well as the accumulation of particles near the meniscus. We should emphasize that we have never observed clogging of the tube for the perfectly wetting fluid considered here, but we have observed, from time to time, the entrainment of some clusters near the entrainment threshold.

V. CONCLUSION

In this article, we have shown that the liquid coating the inner wall of a capillary tube exhibits different regimes in the presence of particles: liquid only and deposition of particles. We demonstrated that a particle is entrained in the film even if its diameter is larger than the film thickness. Considering the thickness at the stagnation point, the experimental results have been quantitatively rationalized. In particular, we have provided some physical insights to rationalize the order of magnitude of the parameter α. A similar physical mechanism underlies the entrainment of particles as observed in both this configuration and in dip coating [START_REF] Colosqui | Hydrodynamically Driven Colloidal Assembly in Dip Coating[END_REF][START_REF] Sauret | Capillary filtering of particles during dip coating[END_REF]. This result comes from the common features between this configuration and the dip-coating of a substrate, the most important of which is the presence of a stagnation point. Therefore, preventing the contamination of substrate by particles and biological microorganisms using this strategy, as reported for the dip coating system [START_REF] Sauret | Capillary filtering of particles during dip coating[END_REF], is also valid in tubings and can provide guidelines for dispensing of suspensions and contaminated liquid in tubes. These results are also relevant to environmental processes involving the transport of small particles in confined geometries, such as the dissemination of colloid and microorganisms in porous media [START_REF] James E Saiers | The role of moving air-water interfaces in colloid mobilization within the vadose zone[END_REF] and provide guidelines to improve the coating of tubings by suspensions [START_REF] Bk Primkulov | Spin coating of capillary tubes[END_REF]. This filtering mechanism could also be an ingredient to explain the increase of bubble rise speed observed recently in confined suspension [START_REF] Madec | Puzzling bubble rise speed increase in dense granular suspensions[END_REF]. The influence of the wettability of the particle can further refine the value of the prefactor and is the topic of an ongoing study.

FIG. 1 .

 1 FIG. 1. (a) Schematic of the experimental setup. (b) Time sequence (top to bottom) of the entrainement of a particle of radius a = 125 µm in the liquid film for U = 4.18 mm.s -1 in a tube of radius R = 0.75 mm (Movie: Supplemental Material). The dashed lines indicate the inner walls of the tube. Scale bar is 400 µm.

FIG. 3 .

 3 FIG. 3. (a) Examples of film and particles deposited for increasing velocity (bottom to top) and two particle radii, 72 µm and 125 µm, in a tube of radius R = 750 µm. Scale bar is 500 µm. (b) Threshold front velocity U * beyond which particles are entrained in the coating film as a function of the particle radius a for tube of radii R = 0.5, 0.75, and 1mm.

FIG. 4 .

 4 FIG. 4. Particle dynamics (R = 0.75 mm, a = 125 µm) in the (a) no deposition regime for U = 2.07 mm.s -1 and (b) deposition regime for U = 3.45 mm.s -1 . The main panels show the time evolution of the position of the front (solid line) and one particle (circles). Top right insets report the evolution of the rescaled absolute velocity of the front (solid line) and the particle (circles). The bottom right insets show the corresponding experimental observations. The small arrows indicate the particle and the scale bars are 500 µm (Movies: Supplemental Material)

FIG. 5 .

 5 FIG. 5. (a) Examples of streamlines and flow field (colormap: |u|/U ) obtained numerically for Ca = 10 -4 , Ca = 10 -3 and Ca = 2 × 10 -2 (from left to right). (b) Zoom on the stagnation point S * . The red dashed line separate the recirculating region where the fluid flow back to the bulk and the film region where the liquid is entrained in the coating film.

FIG. 7 .

 7 FIG. 7. (a)Threshold capillary number Ca * as a function of (a/R) 2 for different radii of the particles and of the tubes. Inset: Comparison with the entrainment thresholds obtained for the dip coating of a plate[START_REF] Sauret | Capillary filtering of particles during dip coating[END_REF], a thin fiber[START_REF] Dincau | Entrainment of particles during the withdrawal of a fibre from a dilute suspension[END_REF] and the present experiments. In both figures the solid line is Eq. (9) with α = 1.15. (b) Thickness at the stagnation point calculated theoretically (knowing the experimental parameters) allowing a particle to be entrained in the coating film as a function of the radius of the particle a. The dashed line shows the linear law: h * th = a. Inset: Entrainement of a 125 µm particle in the coating film (Ca = 6.1 ×10 -2 ) illustrating that an entrained particle can be smaller than the liquid film thickness owing to the deformation of the air/liquid interface. The scale bar is 200 µm.

FIG. 8 .

 8 FIG.8. Schematic of the forces exerted on a particle confined in the liquid at the stagnation point.

ACKNOWLEDGMENTS

This material is based upon work supported by the National Science Foundation under NSF CAREER Program Award CBET No. 1944844 and by the ACS Petroleum Research Fund 60108-DNI9. We thank F. Gallaire and L. Keiser for their help with the numerical model and B. Dincau