Tınaz Ekim
email: tinaz.ekim@boun.edu.tr

Bernard Ries
email: bernard.ries@wbs.ac.uk

Dominique De Werra
email: dominique.dewerra@epfl.ch

Split-critical and uniquely split-colorable graphs

Keywords: Split-coloring, split-critical, uniquely split-colorable, split-decreasing

The split-coloring problem is a generalized vertex coloring problem where we partition the vertices into a minimum number of split graphs. In this paper, we study some notions which are extensively studied for the usual vertex coloring and the cocoloring problem from the point of view of split-coloring, such as criticality and the uniqueness of the minimum split-coloring. We discuss some properties of split-critical and uniquely split-colorable graphs. We describe constructions of such graphs with some additional properties. We also study the effect of the addition and the removal of some edge sets on the value of the split-chromatic number. All these results are compared with their cochromatic counterparts. We conclude with several research directions on the topic.

Introduction

In this paper, we deal with a generalization of the graph coloring problem, called split-coloring. The minimum split-coloring problem in an undirected graph G = (V, E), defined first in [START_REF] Ekim | On split-coloring problems[END_REF], consists of minimizing the integer max(p, k) such that the vertices of G can be partitioned into p cliques and k stable sets. Since empty stable sets or cliques are also allowed, it can be easily seen that this problem is equivalent to partitioning the vertices of G into a minimum number of split graphs (defined as graphs whose vertex set can be partitioned into a clique and a stable set). Thus, here a color stands for a subset of vertices inducing a split graph. The optimal value is denoted by χ S (G) and called split-chromatic number. Clearly, minimum split-coloring is N P-hard in general [START_REF] Ekim | On split-coloring problems[END_REF]. Several papers considered polynomially solvable cases of minimum split-coloring with respect to various graph classes; in cacti be denoted by (K 1 , . . . , K k ; S 1 , . . . , S k ), where K i is a clique, S j is a stable set and K i ∩ S j = ∅, for i, j = 1, . . . , k. Throughout the paper, whenever we say that a split-coloring uses/needs/contains k stable sets (resp. k cliques), these stable sets (resp. cliques) are supposed to be non-empty. For all graph theoretical notions that are not defined here, the reader is referred to [START_REF] Berge | Graphs and hypergraphs[END_REF].

Split-critical graphs

In this section we will present some properties of k-split-critical graphs. In [START_REF] Földes | Split graphs[END_REF], it is shown that split graphs are precisely graphs which do not contain any induced subgraph isomorphic to 2K 2 , C 4 or C 5 . Hence 2K 2 , C 4 and C 5 are the only 2-split-critical graphs. Now, we study some properties concerning the connected components of k-split-critical graphs for k ≥ 3.

Proposition 2.1 Let G be a k-split-critical graph, with k ≥ 3. Then every connected component C of G satisfies χ(C) ≥ k.

Proof: Let C 1 , . . . , C p be the connected components of G. Suppose that there exists C i , i ∈ {1, . . . , p}, which is (k -1)-colorable, i.e., χ(C i ) ≤ k -1, and let S 1,i , . . . , S k-1,i be a (k -1)-coloring of C i . Since G is k-split-critical, it follows that G-V (C i ) is (k-1)-split-colorable. Let (K 1 , . . . , K k-1 ; S 1 , . . . , S k-1 ) be a (k -1)-split-coloring of G -V (C i ). Then by adding S j,i to S j , for j = 1, . . . , k -1, we obtain a feasible (k -1)-split-coloring of G, a contradiction.

2

The following result is an imediate consequence of Proposition 2.1.

Corollary 2.2 Let G be a 3-split-critical graph. Then every connected component C of G contains at least one odd cycle.

Proposition 2.3 Let G be a k-split-critical graph, with k ≥ 3. Then G has at most k connected components.

Proof: Suppose that G has k + 1 connected components C 1 , . . . , C k+1 . Let v ∈ C k+1 . Then G -v is (k -1)-split-colorable. From Proposition 2.1, it follows that every connected component C of G satisfies χ(C) ≥ k. Now if there is a connected component C i , i ∈ {1, . . . , k}, such that the vertices of C i can be colored using only stable sets in a (k -1)-split-coloring of G -v, we would need at least k stable sets, which contradicts the fact that G -v is (k -1)-split-colorable. Thus the vertices of each connected component C 1 , . . . , C k are colored using at least one clique in every (k -1)-split-coloring of G -v. But this means that we have at least k disjoint cliques (hence k different colors) which contradicts the fact that G -v is (k -1)-split-colorable. 2

Proposition 2.4 Let G be a k-split-critical graph, with k ≥ 3. If G contains exactly k -1 connected components C 1 , . . . , C k-1 , then there exists C i , i ∈ {1, . . . , k -1}, which is k-critical.

Proof: From Proposition 2.1 we know that each connected component C i satisfies χ(C i ) ≥ k. Suppose for a contradiction that no C i is k-critical, i.e., for every i = 1, . . . , k -1 there exists v i such that χ(C i -v i ) ≥ k. Since G -v 1 is (k -1)-split-colorable, denote by (K 1 , . . . , K k-1 ; S 1 , . . . , S k-1 ) a (k -1)-split-coloring of G -v 1 . Since χ(C 1 -v 1 ) ≥ k, with an appropriate labeling we have without loss of generality V (K 1 ) ⊆ V (C 1 ). By repeating this argument for a vertex v 2 ∈ V (C 2 ), we deduce that each connected component is (k -1)-split-colorable by partitioning its vertex set into exactly one clique and at most k -1 stable sets. But then G is (k -1)-split-colorable, which is a contradiction. So there exists at least one connected component C i , i ∈ {1, . . . , k -1}, which is k-critical. 2

As an immediate consequence we get the following result.

Corollary 2.5 Let G be a 3-split-critical graph. If G contains exactly two connected components, then one of them is an odd cycle.

Proof: This follows from Proposition 2.4 and from the fact that the only 3-critical graphs are odd cycles. 2

Now using a similar argument as in the proof of Proposition 2.4, one can show the following.

Proposition 2.6 Let G be a k-split-critical graph, with k ≥ 3. If G contains exactly k connected compo- nents C 1 , . . . , C k , then each of them is k-critical.
Corollary 2.7 A graph G is 3-split-critical with 3 connected components if and only if each connected component is an odd cycle.

We will give now a necessary and sufficient condition for a graph to be k-split-critical, with k ≥ 3. First we mention an easy observation which we will need in our proof.

Proposition 2.8 If G is k-split-critical, then G admits a k-split-coloring using exactly k cliques (resp. k stable sets) (with one of them of size one) and at most k -1 stable sets (resp. at most k -1 cliques), with k ≥ 2.

Proof: Suppose that there is a k-split-coloring of G using exactly k cliques and k stable sets. Now consider a vertex v ∈ V (G). By criticality of G we know that G -v is (k -1)-split-colorable. By considering v as a clique (resp. a stable set) we obtain a k-split-coloring of G with at most k -1 stable sets (resp. k -1 cliques).

2

Proposition 2.9 A graph G is k-split-critical if and only if G = (G⊕S k )∪K k+1 is (k +1)-split-critical, with k ≥ 2.
Proof: First assume that G is k-split-critical. Then it follows from Proposition 2.8 that there exists a k-split-coloring of G using k cliques and at most k -1 stable sets. This can be extended to a (k + 1)split-coloring of G by adding the clique K k+1 and the stable set S k ; hence χ S (G ) ≤ k + 1. Suppose χ S (G ) < k + 1, then there is a k-split-coloring of G using at most k stable sets, which can cover at most k vertices of K k+1 . Consequently, one clique which is completely in K k+1 is used. The remaining (at most) k -1 cliques can cover at most k -1 vertices of S k ; hence one stable set which is completely in

S k is used. It follows that G is (k -1)-split-colorable, a contradiction. Thus, χ S (G ) = k + 1.

Let us show now that for all

v ∈ G , we have χ S (G -v) = k. If v ∈ G, then take a (k -1)-split- coloring of G -v, add clique K k+1 and stable set S k to obtain a k-split-coloring of G -v. If v ∈ S k
then take a k-split-coloring of G with k stable sets and at most k -1 cliques (such a k-split-coloring exists by Proposition 2.8). This split-coloring can be extended to cover all vertices of S k -v and all vertices of K k+1 but one; take this uncovered vertex as a new clique, giving a k-split-coloring of G -v. Lastly, if v ∈ K k+1 , the same k-split-coloring of G can be extended to cover all vertices of K k+1 -v and all vertices of S k but one; take this uncovered vertex as a new clique to obtain a k-split-coloring of G -v.

Now let us assume that

G is (k + 1)-split-critical. If χ S (G) < k then take a (k -1)-split-coloring of G, add clique K k+1 and stable set S k to obtain a k-split-coloring of G , a contradiction. Therefore χ S (G) ≥ k. Moreover G is (k + 1)-split-critical and G is an induced subgraph of G ; thus χ S (G) = k. Let us show now that for all v ∈ G, we have χ S (G -v) = k -1. For v ∈ G, take a k-split-coloring of G -v; it
contains at most k stable sets which can cover at most k vertices of K k+1 ; hence it has a clique completely contained in K k+1 . The remaining (at most) k -1 cliques can cover at most k -1 vertices of S k ; hence it has a stable set completely contained in S k . The remaining (at most) k -1 cliques and (at most) k -1 stable sets give a (k -1)-split-coloring of G -v; this concludes the proof.

2

A construction of k-split-critical graphs for k ≥ 2 follows from Proposition 2.9. Take one of the three 2-split-critical graphs, that is, 2K 2 , C 4 or C 5 , and apply recursively k -2 times the transformation described in Proposition 2.9 to obtain a k-split-critical graph. Note that all graphs for k > 2 obtained in this way have two connected components.

The following result gives a construction of triangle-free k-split-critical graphs with p ≤ k connected components.

Theorem 2.10 For every p, 1 ≤ p ≤ k, there exists a k-split-critical triangle-free graph G p,k with p connected components for k ≥ 3.

Proof: We know that the Mycielski graph M k of order k is a triangle-free k-critical graph [START_REF] Mycielski | Sur le coloriage des graphs[END_REF]. G p,k for p = 1, . . . , k is obtained as follows. If p = k, we take a cycle C with edges e 1 , e 2 , . . . , e l , where l = 4(k -p) + 2, such that every even indexed edge belongs to a distinct copy of M k . We also add (p -1)M k (see Figure 1 for an example, where p = 3 and k = 5). If p = k, we simply take kM k . Clearly, G p,k has p connected components.

Notice that G p,k is not (k -1)-split-colorable, otherwise every Mycielski graph must have at least one vertex in a clique of that (k -1)-split-coloring. But clearly we need at least k cliques to do so, a contradiction. Thus χ S (G p,k ) ≥ k. Next we show that G p,k is k-split-colorable by taking as cliques (if p = k) one vertex from each M k in the subgraph (p -1)M k , edges e i , i = 1, 5, 9, . . . , l -5, and the vertex v l-1 which is the common endpoint of e l-2 and e l-1 , summing up to (p -1) + k -p + 1 = k cliques (if p = k take simply k cliques consisting of one vertex from each M k ); then the remaining graph (after removal of these cliques) is (k -1)-colorable by criticality of the M k 's.

Moreover, for every vertex v, G p,k -v is (k -1)-split-colorable. This clearly holds for kM k (in case p = k) by criticality of the M k 's. Now, assume that p = k. Indeed, if v belongs to one of the p -1 disjoint copies of M k , then clearly we need one clique less to split-color G p,k -v and thus χ S (G p,k ) = k -1. Now if v does not belong to any of the p -1 disjoint copies of M k , then we may assume w.l.o.g. that v belongs to the Mycielski graph M k such that v l-1 ∈ M k . Now in G p,k -v, take the same cliques as before except v l-1 . These k -1 cliques of G p,k -v touch (i.e., contain at least one vertex of) all induced M k 's; again by criticality, the remaining graph is

M 5 M 5 M 5 M 5 M 5 M 5 M 5
(k -1)-colorable. It follows that G p,k -v is (k -1)-split-colorable.
2

Note that if triangle-freeness is not required, any k-critical graph can play the role of M k in Theorem 2.10. Finally let us observe the following result.

Proposition 2.11 Let G be a k-critical graph. Then χ S (G) ≤ k -1.

Proof: Suppose G is k-critical and χ S (G) ≥ k. It means that for any vertex v, G -v is (k -1)-colorable. But then there is a (k -1)-split-coloring of G using one clique (vertex v) and (k -1) stable sets, a contradiction.

2

Note that the cochromatic counterpart of Proposition 2.11 does not hold; that is, there are k-critical graphs which are also critically k-cochromatic. In fact, it is shown in [START_REF] Lesniak | The cochromatic number of a graph[END_REF] that every triangle-free graph G with at least 3 vertices has χ(G) = z(G); hence every triangle-free k-critical graph is also critically k-cochromatic; take for instance the Mycielski graphs [START_REF] Mycielski | Sur le coloriage des graphs[END_REF]. Also, in [START_REF] Broere | Critically Cochromatic Graphs[END_REF], for all k ≥ 4, a construction of (not triangle-free) graphs which are both k-critical and critically k-cochromatic is described.

Uniquely split-colorable graphs

In this section we give some properties of uniquely split-colorable graphs. We recall that a graph G is uniquely split-colorable if every optimal split-coloring of G has the same collection of cliques and stable sets. Let us first notice the following result whose cochromatic counterpart is also true [START_REF] Gimbel | Some Topics in Cochromatic Theory[END_REF].

Lemma 3.1 If G is uniquely k-split-colorable then G is not k-split-critical.
Proof: Suppose there is a graph G which is uniquely k-split-colorable and also k-split-critical. By criticality, we have that for every vertex v, there is a k-split-coloring of G where v is a color class by itself. No two such k-split-colorings are the same. Indeed, if two such k-split-colorings are the same, it follows that there exist two vertices, say v and w, such that each of them is a color class by itself. If v and w are non-adjacent (resp. adjacent), we would get a (k -1)-split-coloring by considering {v, w} as a stable set (resp. vw as a clique). Thus we get n different optimal split-colorings of G (where n is the number of vertices in G), contradicting the uniqueness of the split-coloring.

2

The next result gives some necessary conditions for a graph to be uniquely split-colorable.

Proposition 3.2 Let G be a uniquely k-split-colorable graph and let U be its unique partition into stable sets and cliques. Then the following conditions are satisfied:

(1) the union of any two stable sets in U is connected;

(2) the union of any two cliques in U is anticonnected, i.e., connected in the complement;

(3) for every v ∈ K, where K is a clique of U, v has a neighbor in every stable set of U;

(4) for every w ∈ S, where S is a stable set of U, w has a non-neighbor in every clique of U;

(5) the number of stables sets in U is equal to the number of cliques in U.

Proof: The first two conditions respectively follow from the fact that the subgraph induced by the stable sets in U and the complement of the subgraph induced by the cliques in U have unique partitions. The third and forth conditions express that no vertex can be moved from a clique to a stable set or vice versa. The fifth condition is trivially necessary. 2

In Figure 2, we can observe that the five conditions given in Proposition 3.2 are not sufficient. The 2split-coloring ({a, d, 4}, {f, 3, 6}; {5, 1, b}, {e, 2, c}) of this graph satisfies the five conditions of Proposition 3.2 but the graph is not uniquely split-colorable; another 2-split-coloring is obtained by taking the sugbraph induced by vertices a, b, c, d, e, f as one split graph, and the subgraph induced by vertices 1, 2, 3, 4, 5, 6 as the second split graph. We note with the following proposition that conditions (3) and (4) of Proposition 3.2 are also sufficient for a graph G such that χ S (G) = 1, i.e., for a split graph.

Proposition 3.3 Let G = (V, E) be a split graph. Then G has a unique split-partition if and only if its vertices can be partitioned into a clique K and a stable set S such that (1) for every v ∈ K, v has a neighbor in S;

(2) for every w ∈ S, w has a non-neighbor in K.

Proof: From Proposition 3.2 we immediately deduce the necessity of both conditions. Let us show now that (1) and (2) are also sufficient conditions. Let (K 1 , S 1 ) be a split-partition of G for which (1) and (2) are satisfied, and let us assume that there exists another split-partition, denoted by

(K 2 , S 2 ), which is different from (K 1 , S 1 ). Then clearly |V (K 1 ) \ V (K 2 )| = |V (K 2 ) \ V (K 1 )| = 1. So let {v} = V (K 1 ) \ V (K 2 ) and {v } = V (K 2 ) \ V (K 1 ).
From (1) we know that v must have a neighbor in S 1 . But this neighbor is necessarily vertex v , since otherwise we contradict the fact that S 2 is a stable set. So vv ∈ E. But now we have a contradiction with (2) since v, which belongs to S 2 , is adjacent to all vertices in K 2 . 2

Now, let us describe a construction of graphs U k which are uniquely k-split-colorable for k ≥ 2.

Construction: For any k ≥ 2, we construct a graph U k as follows. First, take k graphs G 1 , . . . , G k where each G i is isomorphic to a split graph with unique split-partition (K i k+1 , S i k+1 ) where K i k+1 is a clique on vertices v i 1 , . . . , v i k+1 and S i k+1 is a stable set on vertices u i 1 , . . . , u i k+1 , and the only edges between K i k+1 and

S i k+1 are v i 1 u i 1 , v i 2 u i 2 , . . . , v i k+1 u i k+1
. Now, we also add for i, i = 1, . . . , k and j = 1, . . . , k + 1, edges v i j u i j with i = i and all possible edges between every pair of stable sets S i k+1 , S j k+1 , i = j (hence S 1 k+1 , . . . , S k k+1 induce a complete k-partite graph). See Figure 3 for an example with k = 2.

v 1 1 v 1 2 v 1 3 u 1 1 u 1 2 u 1 3 u 2 1 u 2 2 u 2 3 v 2 1 v 2 2 v 2 3 Fig. 3: The graph U2. Theorem 3.4 For k ≥ 2, U k is uniquely k-split-colorable.
Proof: A k-split coloring U of U k is obtained by taking each G i as a split graph. Assume there exists a different k-split-coloring U of U k . Now, every clique in U contains at least one vertex in some clique of U since otherwise we would need k + 1 stable sets to cover all vertices of some clique K i k+1 of U. Thus each one of the k cliques in U contains at least one vertex from a clique K i k+1 of U. Moreover, there is at least one clique K in U containing some vertices of K i k+1 for some i, say K I k+1 , which also contains at least one vertex from a stable set of U. Indeed if all cliques of U are subsets of K i k+1 , i = 1, . . . , k, with at least one proper subset (since U is different from U ) then k stable sets cannot cover the remaining vertices (the only way to partition vertices u i j , i = 1, . . . , k, j = 1, . . . , k + 1, into stable sets is to take S i k+1 , i = 1, . . . , k, which does not include any vertex from the cliques K i k+1 , i = 1, . . . , k). Now we can assume without loss of generality that the clique K is maximal and hence is formed by v I J , u 1 J , u 2 J , . . . , u k J for some J ∈ {1, . . . , k + 1}. Indeed, if K is not maximal then one can make it maximal by adding new vertices, and this would still give us a different k-split-coloring than U. Also, as already pointed out, the remaining k -1 cliques of U contain at least one vertex from each clique K i k+1 , i = 1, . . . , k, i = I. Then, since K is different from all cliques in U (and thus U is different from U), we may assume without loss of generality that each of these cliques (except K) is either K i k+1 , for some i = I, or formed by one vertex in K i k+1 , for some i = I, and one vertex from each stable set S J k+1 for J = 1, . . . , k. Notice that

((U k -V (K)) -∪ i =I V (K i k+1 )) contains k vertex disjoint cliques formed by one vertex in K I k+1
different from v I J and one vertex from each stable set S J k+1 , J = 1, . . . , k; at least one of these cliques of size k + 1 remains untouched (i.e., none of its vertices is contained in some clique of U ). Clearly the vertices of this clique cannot be partitioned into k stable sets. Therefore, U cannot be a k-split-coloring. 2

Adding/deleting edges

In [START_REF] Gimbel | Some Topics in Cochromatic Theory[END_REF], the variation of the cochromatic number when we remove an edge is studied. Here, instead of a single edge, we first consider the removal of the edges of a C 4 , 2K 2 or a C 5 since these are the only minimal forbidden induced subgraphs for split graphs. Let G be a graph and let H be an induced subgraph of G. We denote by V (H) (resp. E(H)) the vertex set (resp. edge set) of H, and by G -E(H) the graph obtained from G by deleting the edges of H. Let H be a graph and let S be the set of stable sets in G of size |V (H )|. We denote by G + E(H ) the graph obtained from G by adding the edges of a graph isomorphic to H using the vertices of some S ∈ S. If two vertices u, v are not adjacent in a graph G, we say that e = uv is a missing edge of G.

Proposition 4.1 Let G = (V, E) be a graph and let H be an induced subgraph of G isomorphic to either

C 4 , 2K 2 or C 5 . Then χ S (G) -1 ≤ χ S (G -E(H)) ≤ χ S (G) + 1.
Proof: Consider an optimal split-coloring of G. Now in G -E(H), where H is isomorphic to either C 4 or 2K 2 or C 5 , V (H) forms a stable set. Thus by introducing a new color which corresponds to this stable set, we get a feasible split-coloring of G -E(H) with χ S (G) + 1 colors and hence χ S (G -E(H)) ≤ χ S (G) + 1.

Consider now G -E(H) with H being isomorphic to a C 5 (the proofs are similar for the case where H is isomorphic to C 4 or 2K 2 ). Let E(H) = {ab, bc, cd, de, ae}. Suppose that G -E(H) admits a split-coloring U using at most χ S (G) -2 colors. Then we obtain a (χ S (G) -1)-split-coloring of G by first uncoloring vertices a, b and d and by adding to U one new color consisting of the stable set {d} and the clique {ab}, a contradiction. Thus χ S (G) -1 ≤ χ S (G -E(H)).

2

Proposition 4.2 Let G = (V, E) be a graph and let H be a graph isomorphic to either

C 4 , 2K 2 or C 5 . Then χ S (G) -1 ≤ χ S (G + E(H)) ≤ χ S (G) + 1. Proof: First notice that χ S (G) = χ S (G)
, where G denotes the complement of G. Indeed, this follows from the fact that the complement of a clique is a stable set and vice versa. Next observe that

G + E(H) = G -E(H). Thus χ S (G + E(H)) = χ S (G + E(H)) = χ S (G -E(H)). It follows from Proposition 4.1 that χ S (G) -1 ≤ χ S (G + E(H)) ≤ χ S (G) + 1. Now we conclude using the fact that χ S (G) = χ S (G). 2
In what follows we will concentrate on the properties of adding any missing edge or removing any existing edge in a graph. A vertex u of a graph G is called universal if u is adjacent to all the vertices in G -u. 2

Since χ S (G) = χ S (G) and G + e is isomorphic to G -e, Proposition 4.3 can also be expressed as follows: if G has no universal vertex and if G is such that the removal of any edge decreases χ S (G) = k then G is k-split-critical. This result is in parallel with its cochromatic counterpart [START_REF] Gimbel | Some Topics in Cochromatic Theory[END_REF]. We also note that the converse of Proposition 4.3 is not true as can be observed in Figure 4.

One can easily observe the following since the only 2-split-critical graphs are 2K 2 , C 4 and C 5 .

Corollary 4.4 A graph G with χ S (G) = 2 is such that the addition of any missing edge decreases its split-chromatic number if and only if it is isomorphic to a 2K 2 , a C 4 or it is obtained from 2K 2 or C 4 by adding universal vertices.

Unlike to its cochromatic counterpart, we notice the following.

Proposition 4.5 There is no graph G such that addition of any missing edge increases χ S (G).

Proof: Suppose G is such that the addition of any missing edge increases χ S (G) = k. This implies that for every pair of non-adjacent vertices u, v in G, all k-split-colorings of G have a stable set containing both u and v. Indeed, if there exists a k-split-coloring U of G in which u, v do not belong to the same stable set, then U is also a feasible k-split-coloring of G + e, a contradiction. It follows that G is P 3 -free, where P 3 is an induced path on three vertices. In fact, if x 1 , x 2 , x 3 induce a P 3 with x 1 adjacent to x 2 , then x 1 , x 3 and x 2 , x 3 are in the same stable set in all k-split-colorings by the previous observation, a contradiction since x 1 is adjacent to x 2 . Thus G is necessarily a complete k-partite graph. But now one can see that adding any missing edge e = uv does not increase χ S (G). Indeed we get a k-split-coloring of G + e by taking u, v as a clique and partitioning the remaining vertices into k stable sets. 2

Let G = (V, E) be a graph with χ S (G) = k and such that χ s (G + e) = k -1 for any missing edge e in G and χ S (G -e ) = k -1 for any edge e ∈ E. Then G is called split-decreasing.

The following result gives a construction of split-decreasing graphs.

Theorem 4.6 For every p, 1 ≤ p ≤ k, there exists a split-decreasing graph G k,p = (V, E) with p connected components for k ≥ 2 and χ S (G k,p ) = k. This graph G k,p is isomorphic to (p -1)K k ∪ kK k-p+1 .

Proof: Consider the graph G k,p , for 1 ≤ p ≤ k, as described above. Denote by

K 1 k , . . . , K p-1 k the cliques of the subgraph (p -1)K k . Clearly χ S (G k,p ) = k. Indeed, χ S (G k,p ) ≤ k since k cliques can partition G k,p . Moreover, χ S (G k,p ) > k -1 since k -1 stable
sets leave uncovered at least one vertex from each K i k , i = 1, . . . , p -1, which induce a stable set of size k that cannot be partitioned with k -1 cliques. Now assume we add a missing edge e to kK k-p+1 . Notice that kK k-p+1 is a complete k-partite graph, each of the stable sets S 1 , . . . , S k having size k -p + 1. Denote by u 1 i , . . . , u k-p+1 i the vertices of stable set S i , i = 1, . . . , k. We may assume that e = u 1 1 u 2 1 . Then we get a (k -1)-split coloring of G k,p + e by taking p -

1 cliques K 1 k , . . . , K p-1 k
, a clique corresponding to e as well as k -p -1 cliques each of them being a vertex of S 1 -{u 1 1 , u 2 1 }, and by taking k -1 stable sets S 2 , . . . , S k . If we add a missing edge e = uv between two cliques, say

K 1 k and K 2 k with u ∈ K 1 k and v ∈ K 2 k , then we obtain a (k -1)-split-coloring of G k,p + e by taking p -3 cliques K 3 k , . . . , K p-1 k
, a clique corresponding to edge e as well as k-p+1 cliques in kK k-p+1 (each such clique is induced by u j 1 , . . . , u j k , for j = 1, . . . , k -p + 1), and finally k -1 stable sets, each of them corresponding to two vertices, one in K 1 k -u and the other in

K 2 k -v.
Suppose we add an edge e between a clique, say K 1 k , and kK k-p+1 . We may assume that e = vu 1 1 , where v ∈ K 1 k . Then take p -2 cliques K 2 k , . . . , K p-1 k , a clique corresponding to edge e as well as k -p cliques each corresponding to one vertex of S 1 -u 1 1 , and k -1 stable sets S 2 , . . . , S k , each one together with one vertex from K 1 k -v. This gives us a (k -1)-split coloring of G k,p + e. If we delete an edge e = uv from a clique, say K 1 k , then a (k -1)-split coloring of G k,p -e is obtained by taking p -2 cliques K 2 k , . . . , K p-1 k , k -p + 1 cliques partitioning kK k-p+1 , and k -1 stable sets, one corresponding to the vertices u, v, and k -2 corresponding each to a different vertex of K 1 k -{u, v}. Finally the last case to consider is when we delete an edge e from kK k-p+1 . W.l.o.g we may assume that e = u 1 1 u 1 2 . Then by taking p -

1 cliques K 1 k , . . . , K p-1 k , k -p cliques of kK k-p+1
(each clique is induced by vertices u j 1 , . . . , u j k for j = 2, 3, . . . , k -p + 1), and k -1 stable sets, one corresponding to vertices u 1 1 , u 2 1 and k -2 corresponding each to a vertex u 1 i , i = 3, . . . , k, we obtain a (k -1)-split coloring of G k,p -e.

2

We also observe the following two properties. Then G is split-decreasing if and only if G is isomorphic to kK k .

Proof: From Theorem 4.6 we know that if G is isomorphic to kK k , then G is split-decreasing (G k,k in Theorem 4.6 is isomorphic to kK k ). Suppose now that G has k connected components C 1 , . . . , C k , χ S (G) = k, and G is split-decreasing. Clearly if C i is a clique for i = 1, . . . , k, then each C i has size at least k (otherwise χ S (G) < k). Moreover, if there exist C i isomorphic to K k , k > k, then G -e, where e ∈ E(K k ), still contains kK k as a subgraph, hence χ S (G -e) ≥ k, and thus G is not split-decreasing, a contradiction. Now let us assume that there is at least one connected component, say C 1 , which is not a clique. Then uv ∈ E for some u, v ∈ V (C 1 ). Since G is k-split-critical (see Proposition 4.3), we deduce from Proposition 2.1 that χ(C i ) ≥ k. Now consider G + uv. Since χ S (G + uv) = k -1, we deduce that in any (k -1)-splitcoloring we need exactly one clique in each component C 2 , . . . , C k . Furthermore uv must be in a clique. In fact if uv is not in a clique then the (k -1)-split-coloring of G + uv is also a (k -1)-split-coloring of G, a contradiction. But then we get k cliques in the (k -1)-split-coloring of G + uv, which is also a contradiction. Thus all connected components are cliques of size k.

2

We will now concentrate on graphs G with at least two connected components that are split-decreasing and have split-chromatic number χ S (G) = 3. Since these graphs are 3-split-critical (see Proposition 4.3; clearly G has no universal vertex and there necessarily exist two non-adjacent vertices), it follows from Proposition 2.3 that they have at most three connected components. Proposition 4.8 gives a caracterization of all 3-split-colorable graphs that are split-decreasing with three connected components. In fact, there is a unique such graph: each connected component is isomorphic to K 3 . In what follows we will study the case of 3-split-colorable graphs that are split-decreasing and have exactly two connected components. Lemma 4.9 Let G be a graph with two connected components and χ S (G) = 3. If G is split-decreasing, then one of its connected components is isomorphic to K 3 .

Proof: Since G has no universal vertex, we can apply Proposition 4.3 and thus it follows that G is 3split-critical. Corollary 2.5 implies that one of the two connected components is an induced odd cycle C. Clearly, C cannot have length ≥ 5, since adding a missing edge (a chord) between two vertices of C will not decrease χ S (G). In fact, in that case we would still need either one clique and two stable sets or two cliques to cover the vertices of C in any split-coloring. Thus one connected component is isomorphic to

K 3 . 2
In what follows, if G is a split-decreasing graph with two connected components and χ S (G) = 3, we denote by C 1 , C 2 the two connected components of G. Moreover, from Lemma 4.9, we may assume that C 1 is isomorphic to a K 3 .

The following two lemmas represent the main tool that we will use in order to prove the main result of this section. We will repeatedly refer to these lemmas in the remaining of the paper.

Lemma 4.10 Let G be a split-decreasing graph with two connected components and χ S (G) = 3. Then C 2 + e, where e = xy is a missing edge in C 2 , contains a clique K such that x, y ∈ V (K) and (C 2 + e) -V (K) is bipartite (not reduced to a stable set).

Proof: Since G is split-decreasing, G + e is 2-split-colorable. In addition, any 2-split-coloring of G + e uses two cliques and two stable sets, otherwise G would be 2-split-colorable. Clearly one clique of any 2-split-coloring of G + e must be contained in C 1 . Thus, the other clique, denoted by K, is necessarily such that (C 2 + e) -V (K) is bipartite. Moreover, K contains the new edge e = xy. In fact, if K does not contain e, then the 2-split-coloring of G + e is also a feasible 2-split-coloring of G, a contradiction. Furthermore (C 2 + e) -V (K) is not a stable set, since any 2-split-coloring of G + e must use two cliques and two stable sets (as mentioned above). 2

Lemma 4.11 Let G be a split-decreasing graph with two connected components and χ S (G) = 3. Then C 2 -e, where e = xy is an edge in C 2 , contains a stable set S such that x, y ∈ V (S) and (C 2 -e)-V (S) is a split graph (which is not reduced to a clique or a stable set).

Proof: Since G is split-decreasing, G -e is 2-split-colorable. In addition, any 2-split-coloring of G -xy uses two cliques and two stable sets, otherwise G would be 2-split-colorable. Clearly one clique of any 2-split-coloring of G -e must be contained in C 1 . Then C 2 -e can be partitioned into one clique and two stable sets. Suppose none of the two stable sets contains both x and y. Then the 2-split coloring of G -e is also a feasible 2-split-coloring of G, a contradiction. So there is a stable set S containing both

x and y such that (C 2 -e) -V (S) is a split graph. Moreover, (C 2 -e) -V (S) cannot be a clique or a stable set, since this would mean that G is 2-split-colorable, a contradiction. 2

Let C be an induced cycle of a graph G. Let v 1 , . . . , v p be the vertices of C in clockwise order. A vertex

v ∈ V (G) is called a center of C if v is adjacent to all the vertices of C. A vertex w ∈ V (G) \ V (C) is called a clone of some vertex v i ∈ V (C) with respect to C if w is adjacent to v i-1 , v i+1
and not adjacent to V (C) \ {v i-1 , v i+1 }; we will simply say clone of v i whenever no confusion on the cycle is possible. Denote by N (v) the set of neighbors of v, and by N (v) the set of non-neighbors of v.

We first obtain the following result.

Theorem 4.12 Let G be a split-decreasing graph with two connected components and χ S (G) = 3. Then G does not contain any induced cycle of length 2k + 1, k ≥ 2.

Proof: Suppose for a contradiction that C 2 contains an induced cycle

C of length 2k + 1, k ≥ 2. Let v 1 , v 2 , .
. . , v 2k+1 be the vertices of C in clockwise order. We will prove several claims.

Claim (i) Let v ∈ V (C 2 ) \ V (C) such that N (v) ∩ V (C) = ∅.
Then v has exactly one of the following properties.

(1) k = 2, and v is a center of C;

(2) v is a clone of some vertex v i ∈ V (C), i ∈ {1, . . . , 2k + 1};

(3) v is adjacent to exactly one vertex in V (C).

Let v ∈ V (C 2 ) \ V (C) such that N (v) ∩ V (C) = ∅. Suppose that v is not a center of C.
Suppose that v is adjacent to two consecutive vertices of C, say v 1 , v 2 . It follows from Lemma 4.10 that if we add the edge v 3 v 2k+1 , then there exists a clique K in C 2 + v 3 v 2k+1 containing v 3 and v 2k+1 , and such that (C 2 + v 3 v 2k+1 ) -V (K) is bipartite. This implies that v must be adjacent to both v 3 and v 2k+1 otherwise K does not contain any of the vertices v, v 1 , v 2 and hence

(C 2 + v 3 v 2k+1 ) -V (K) contains a K 3 induced by v, v 1 , v 2 ,
a contradiction. Now we may repeat this argument, by applying Lemma 4.10 to the edge v 1 v 4 , and we conclude that v must be adjacent to vertex v 4 . Continuing this procedure we conclude that v must be adjacent to all the vertices in V (C). But now v is a center of C, a contradiction. It follows that v is not adjacent to two consecutive vertices in V (C). This proves the claim for the case k = 2. Thus we may assume now that k ≥ 3.

Suppose that v is adjacent to at least two vertices in V (C), such that v is not a clone of some vertex of V (C), and v is not adjacent to two consecutive vertices in V (C). Since C has odd length, there necessarily exist two neighbors of v in V (C), say v i , v j such that v is non-adjacent to all the vertices in one of the two paths in C joining v i and v j , and such that this path together with edges vv i , vv j is an induced odd cycle C . Now consider x, y ∈ V (C) \ V (C ), with x being adjacent to v i and y being adjacent to v j . Notice that x = y, otherwise v is a clone of x (resp. y), a contradiction. Furthermore x and y are not adjacent, otherwise C has even length, a contradiction. It follows from Lemma 4.10 that if we add the edge xy, there exists a clique K in C 2 + xy containing both x and y, and such that

(C 2 + xy) -V (K) is bipartite. But clearly K does not contain any vertex from V (C ). Thus (C 2 + xy) -V (K) contains C , a contradiction. This proves for k ≥ 3 that if v is a vertex in V (C 2 ) \ V (C) such that N (v) ∩ V (C) = ∅ and v is not a center, then either |N (v) ∩ V (C)| = 1 or v is a clone of some vertex v i ∈ V (C).
Finally we need to prove that if k ≥ 3, v is not a center of C. Suppose for a contradiction that v is a center of C. It follows from Lemma 4.11 that if we delete the edge vv 1 , there exists a stable set S in C 2 -vv 1 containing both v and v 1 , and such that (C 2 -vv 1 ) -V (S) is a split graph. Since v is a center of C, it follows that v 2 , . . . , v 2k+1 ∈ S. But now v 2 , v 3 , v 2k , v 2k+1 induce a 2K 2 , a contradiction. Thus C does not have a center if k ≥ 3. This proves Claim (i).

Claim (ii) If k = 2 and there exists a center v of C, then v is not adjacent to any vertex in V (C 2 ) \ V (C).

Let v be a center of C, and suppose that v is adjacent to some vertex w ∈ V (C 2 ) \ V (C). It follows from Lemma 4.11 that if we delete the edge vw, there exists a stable set S in C 2 -vw containing both v and w, and such that (C 2 -vw) -V (S) is a split graph. Since v is a center of C, it follows that v 1 , . . . , v 5 ∈ S. But then (C 2 -vw) -V (S) contains an induced C 5 , namely C, a contradiction. This proves Claim (ii).

Claim (iii) If k = 2, and there exists a center v of C, then all vertices in V (C 2 ) \ V (C) are centers.

Suppose the claim is false. Then since C 2 is connected, there exists w ∈ V (C 2 ) \ V (C), w = v, such that w is not a center and N (w) ∩ V (C) = ∅. It follows from Claim (i) that either w is a clone or w has exactly one neighbor in V (C). Thus w is non-adjacent to at least two consecutive vertices in V (C), say v 1 , v 2 . From Claim (ii) it follows that v and w are not adjacent. It follows from Lemma 4.10 that if we add the edge v 1 w, there exists a clique K in C 2 + v 1 w such that K contains both v 1 and w, and such that (C 2 + vw) -V (K) is bipartite. Clearly K does not contain any of the vertices v, v 2 , v 3 . But this implies that (C 2 + v 1 w) -V (K) contains the clique induced by v, v 2 , v 3 , a contradiction. This proves Claim (iii).

Claim (iv) If there exists a clone v of some vertex v i ∈ V (C), then every vertex in V (C 2 ) \ V (C) is adjacent to at least one of the vertices v i-1 , v i , v i+1 , for i ∈ {1, . . . , 2k + 1} taken modulo 2k + 1.
Suppose the claim is false. Then there exists a vertex w ∈

V (C 2 ) \ V (C) non-adjacent to v i-1 , v i , v i+1 .
It follows from Lemma 4.10 that if we add the edge wv i , there exists a clique K in C 2 + wv i containing w and v i , and such that (C 2 + wv i ) -K is bipartite. But clearly K does not contain any vertex from the odd cycle induced by (V (C) \ {v i }) ∪ {v}. Thus (C 2 + wv i ) -V (K) contains an odd cycle, a contradiction. This proves Claim (iv).

Claim (v) There exists at most two consecutive vertices in V (C) for which there exist clones in C 2 . Suppose that there exist three consecutive vertices in V (C), say v 1 , v 2 , v 3 , for which there exist clones in C 2 . Let w i be a clone of v i , for i = 1, 2, 3. First notice that w 1 , w 3 are both adjacent to w 2 . Indeed, if for instance w 1 is not adjacent to w 2 , then it follows from Lemma 4.10 that if we add the edge w 1 w 2 , there exists a clique K in C 2 + w 1 w 2 containing w 1 and w 2 and such that (C 2 + w 1 w 2 ) -V (K) is bipartite. But K clearly does not contain any vertex from C. It follows that (C 2 + w 1 w 2 ) -V (K) contains C, a contradiction. Thus w 1 , w 3 are adjacent to w 2 . Moreover we claim that w 1 and w 3 are not adjacent. Suppose for a contradiction that w 1 is adjacent to w 3 . From Lemma 4.10 we deduce that if we add the edge v 1 v 2k , there exists a clique K in C 2 + v 1 v 2k containing v 1 and v 2k , and such that

(C 2 + v 1 v 2k ) -V (K) is bipartite. But K clearly does not contain any of the vertices w 1 , w 2 , w 3 , thus (C 2 + v 1 v 2k ) -V (K)
contains a K 3 induced by w 1 , w 2 , w 3 , a contradiction. Thus w 1 and w 3 are not adjacent. But now it follows from Lemma 4.10 that if we add the edge w 1 w 3 , there exists a clique K in C 2 + w 1 w 3 containing both w 1 and w 3 , and such that (C 2 +w 1 w 3 )-V (K) is bipartite. But K does not contain v 1 , v 3 , . . . , v 2k+1 and either does not contain v 2 or does not contain w 2 . Hence C 2 -V (K) contains an induced odd cycle (either C or the odd cycle induced by v 1 , w 2 , v 3 , . . . , v 2k+1 ), a contradiction. This proves Claim (v).

Claim (vi) There exists at most 2 distinct vertices of V (C) having neighbors in V (C 2 ) \ V (C) which are not centers of C and not clones of some vertices of V (C).

Suppose the claim is false. Let v i , v j , v l be three distinct vertices of V (C) such that each one has a neighbor in V (C 2 ) \ V (C). Let w i be such a neighbor of v i , w j such a neighbor of v j , and w l such a neighbor of v l . From Claim (i) it follows that w i , w j , w l have each exactly one neighbor in V (C). First we claim that w i , w j , w l induce a K 3 . Suppose that they do not induce a K 3 . Assume that w i , w j are not adjacent. Then from Lemma 4.10 it follows that if we add the edge w i w j , there exists a clique K in C 2 + w i w j containing w i and w j , and such that (C 2 + w i w j ) -V (K) is bipartite. But K clearly does not contain any vertex of V (C). Thus (C 2 + w i w j ) -V (K) contains C, a contradiction. Thus we may assume that w i , w j , w l induce a K 3 . Now from Lemma 4.10 it follows that if we add any edge

v i v j with v i , v j ∈ V (C), there exists a clique K in C 2 + v i v j containing v i , v j , and such that (C 2 + v i v j ) -V (K) is bipartite. But clearly K does not
contain any of the vertices w i , w j , w l . Hence C 2 -V (K) contains a K 3 , a contradiction. This proves Claim (vi).

We will now distinguish two cases: k ≥ 3 and k = 2.

Case k ≥ 3: It follows from claims (i), (iv), (v), and (vi) that there exist at least two consecutive vertices in V (C) which have degree exactly two. Indeed, suppose for a contradiction that there exist no two such vertices. From Claim (i) it follows that every vertex v ∈ V (C 2 ) \ V (C) is either a clone of some vertex in V (C) or adjacent to exactly one vertex in V (C). Suppose that there exists a clone v of some vertex in V (C), say v 1 . Then it follows from claims (iv) and (v) that at least one of v 3 , v 6 has degree two. Without loss of generality, we may assume that v 3 has degree two. Thus v 4 must have a neighbor in V (C 2 ) \ V (C). It follows from Claim (iv) that this neighbor must be a clone of vertex v 3 . Now it also follows from Claim (iv) that neither v 5 nor v 6 can have a neighbor in V (C 2 ) \ V (C). But this contradicts the hypothesis that there exist no two consecutive vertices of degree two. Thus we conlcude that there must exist at least two consecutive vertices in V (C) of degree two. Let v 1 , v 2 be these two vertices. This implies that v 1 , v 2 belong to the same induced odd cycles in C 2 . It follows from Lemma 4.10 that if we add the edge v 1 v 3 , there exists a clique K in C 2 + v 1 v 3 containing v 1 , v 3 , and such that (C 2 + v 1 v 3 ) -V (K) is bipartite. Clearly K is isomorphic to K 3 and induced by v 1 , v 2 , v 3 . Thus every induced odd cycle contains at least one of the vertices v 1 , v 2 , v 3 . But since v 1 , v 2 belong to the same odd induced cycles, it follows that C 2 -v 2 v 3 is bipartite, a contradiction with χ S (G) = 3.

Case k = 2: If there exists a center w 1 of C, then it follows from claims (ii) and (iii) that all vertices in V (C 2 ) \ V (C) are centers of C, and all these centers are pairwise non-adjacent. Assume there exist at least two centers w 1 , w 2 . Then it follows from Lemma 4.10 that if we add the edge v 1 v 3 , there exists a clique K in C 2 + v 1 v 3 containing v 1 and v 3 , and such that (C 2 + v 1 v 3 ) -V (K) is bipartite. But K clearly does not contain both w 1 and w 2 . So we may assume without loss of generality that K does not contain w 2 . Thus there exists a clique isomorphic to K 3 in (C 2 + v 1 v 3 ) -V (K) induced by w 2 , v 4 , v 5 , a contradiction. So we may assume now that there exists at most one center of C. But then this center together with v 1 , v 2 forms a clique K such that C 2 -V (K) is bipartite. This contradicts the fact that χ S (G) = 3. Thus we may assume now that there exists no center of C.

If there exists no clone of some vertex of V (C), then we get a contradiction. Indeed, Claim (vi) implies that there exist at least two consecutive vertices in V (C) having degree two. Now we get the contradiction by applying the same argument as in the case k ≥ 3. So suppose that there exists at least one clone of some vertex in V (C). Assume that w 1 is a clone of v 1 . From Claim (v) it follows that we may assume that there exists no clone for vertex v 2 . From Lemma 4.10 it follows that if we add the edge v 1 v 3 , there exists a clique K in C 2 + v 1 v 3 containing both v 1 and v 3 , and such that (C 2 + v 1 v 3 ) -V (K) is bipartite. Clearly K is isomorphic to K 3 , and induced by v 1 , v 2 , v 3 . Thus every induced odd cycle contains at least one of the vertices v 1 , v 2 , v 3 . Repeating the same argument by replacing v 1 by v 4 and v 3 by v 2 , we obtain that every induced odd cycle contains at least one of the vertices v 2 , v 3 , v 4 (resp. one of the vertices v 2 , w 3 , v 4 , where w 3 is a clone for v 3 ). But now we claim that C 2 -v 2 v 3 is bipartite. If not, then there necessarily exists an induced odd cycle containing both v 1 and v 4 , and not containing v 2 , v 3 . Clearly this cycle does not contain a clone of vertex v 3 , otherwise it must contain v 2 , a contradiction. Thus the only vertices adjacent to v 4 which can belong to this cycle are either clones of v 5 or v 5 itself. But these vertices are all adjacent to v 1 , contradicting the odd length of the cycle.

This proves Theorem 4.12. 2

Next we prove that a split-decreasing graph with two connected components cannot contain any induced cycle of even length at least six.

Theorem 4.13 Let G be a split-decreasing graph with two connected components and χ S (G) = 3. Then G does not contain any induced cycle of length 2k, k ≥ 3.

Proof: Suppose for a contradiction that C 2 contains an induced cycle C of length 2k, for some k ≥ 3. Let v 1 , v 2 , . . . , v 2k be the vertices of C in clockwise order. From Theorem 4.12 it follows that C 2 does not contain any induced odd cycles of length 2k + 1, k ≥ 2. Thus the only odd induced cycles in C 2 are triangles. First notice that there exists no center of C and there exists no vertex v ∈ V (C 2 ) \ V (C) that is adjacent to 2 consecutive vertices in V (C). This can be shown by using exactly the same arguments as in the proof of Claim (i) of Theorem 4.12 (due to the length of this proof, we do not repeat these same arguments here). Now from Lemma 4.10 it follows that if we add the edge v 3 v 5 , there exists a clique K in C 2 + v 3 v 5 containing both v 3 and v 5 , and such that (C 2 + v 3 v 5 ) -V (K) is bipartite. Since there is no vertex adjacent to two consecutive vertices in V (C), it follows that K is induced by v 3 , v 4 , v 5 (resp. by v 3 , w 4 , v 5 , where w 4 is a clone for v 4 ). Thus every triangle in C 2 contains at least one vertex among v 3 , v 4 , v 5 (resp. v 3 , w 4 , v 5 ). By repeating this argument for vertices v 2k , v 2 , we deduce that every triangle contains a vertex among v 2k , v 1 , v 2 (resp. v 2k , w 1 , v 2 , where w 1 is a clone for v 1 ). But this implies that every triangle contains both v 2 , v 3 (or v 5 , v 6 in the case where k = 3). This contradicts the fact that no vertex in V (C 2 ) \ V (C) is adjacent to two consecutive vertices in V (C). This proves Theorem 4.13. 2

Our next result states that a split-decreasing graph with two connected components is not a chordal graph.

Theorem 4.14 Let G be a split-decreasing graph with two connected components and χ S (G) = 3. Then G contains an induced cycle of length four.

Proof: It follows from Lemma 4.9 and Theorems 4.12 and 4.13 that C 1 is isomorphic to K 3 , and that C 2 does not contain any induced cycle of length at least 5. Suppose for a contradiction that C 2 does not contain any induced cycle of length four, thus that C 2 is chordal. From [START_REF] Dirac | On rigid circuit graphs[END_REF] we know that every chordal graph has a simplicial vertex, i.e, a vertex whose neighbors induce a clique. Let v be such a simplicial vertex in C 2 . Clearly N (v), N (v) = ∅ since C 2 is connected and C 2 is not a clique. Let x 1 ∈ N (v). It follows from Lemma 4.10 that if we add the edge vx 1 there exists a clique K in C 2 + vx 1 containing both v and x 1 , and such that (C 2 + vx 1 ) -V (K) is bipartite. Clearly K is induced by D(x 1 ) ∪ {v, x 1 }, where D(x 1 ) ⊆ N (v) is the set of neighbors of x 1 in N (v) (we may assume K maximal without loss of generality). We may assume that D(x 1 ) = ∅ since there exists at least one vertex in N (v) which is adjacent to some vertex in N

(v) (otherwise C 2 is not connected). It follows that |N (v) \ D(x 1 )| ≤ 2. Since C 2 -(D(x 1 ) ∪ {x 1 }) is not bipartite (otherwise G would be 2-split-colorable) and (C 2 + vx 1 ) -V (K) is bipartite, it follows that |N (v) \ D(x 1 )| = 2. This holds for any vertex x ∈ N (v) which is adjacent to some vertex in N (v). Let N (v) \ D(x 1 ) = {w 1 , w 2 }. Furthermore, since C 2 -(D(x 1 )∪{v})
is not bipartite (otherwise G would be 2-split-colorable) and since (C 2 +vx 1 )-V (K) is bipartite, it follows that there exist x 2 , x 3 ∈ N (v) such that x 1 , x 2 , x 3 induce a graph isomorphic to K 3 . Let d ∈ D(x 1 ). From Lemma 4.11 it follows that if we delete the edge vd, there exists a stable set S in C 2 -vd containing both v and d, and such that (C 2 -vd) -V (S) is a split graph. Thus the vertices w 1 , w 2 , x 1 , x 2 cannot induce a graph isomorphic to 2K 2 . It follows that x 2 is adjacent to at least one of the vertices w 1 , w 2 . We may assume without loss of generality that x 2 is adjacent to w 2 . We claim that x 2 is adjacent to all the vertices in D(x 1 ). If not, then let d ∈ D(x 1 ) be non-adjacent to x 2 . Then x 2 , w 2 , d, x 1 induce a cycle of length four, a contradiction. Thus x 2 is adjacent to all the vertices in D(x 1 ) ∪ {w 2 }. It follows that x 2 has at most one non-neighbor in N (v), i.e., |N (v) \ D(x 2 )| ≤ 1, where D(x 2 ) is the set of neighbors of x 2 in N (v). But this contradicts the fact that for every vertex x ∈ N (v) which has a neighbor in N (v) we have |N (v) \ D(x)| = 2. This proves Theorem 4.14.

2

We are now in position to prove our main result about split-decreasing graphs.

Theorem 4.15 Let G be a graph with two connected components C 1 , C 2 and χ S (G) = 3. Then G is split-decreasing if and only if C 1 is isomorphic to K 3 and C 2 is isomorphic either to 3K 2 or to C 4 ∪ K 2 (see Figure 5). Proof: First suppose that G is split-decreasing. It follows from Lemma 4.9 that C 1 is isomorphic to K 3 . Suppose for a contradiction that C 2 is isomorphic neither to 3K 2 nor to C 4 ∪ K 2 . It follows from Theorems 4.12 ,4.13 and 4.14 that C 2 contains an induced cycle C of length four, but no induced cycle of length k ≥ 5. Let {v 1 v 2 , v 2 v 3 , v 3 v 4 , v 4 v 1 } be the edge set of C. In what follows we will prove several claims.

(resp. w, w, v 1 , v 2 ∈ V (S)), but they induce a graph isomorphic to 2K 2 , a contradiction. Now assume that two vertices w ∈ V 12 and w ∈ V 34 are adjacent. Then by applying Lemma 4.11 to the edge ww we conclude that (C 2 -ww ) -V (S) is a split graph, where S is a stable set containing w, w . But clearly (C 2 -ww ) -V (S) contains C, a contradiction. Next let us prove that no vertex in V 12 is adjacent to a vertex in V 13 (resp. V 24 ). From the symmetry it will follow that no vertex in V 34 is adjacent to a vertex in V 13 (resp. V 24 ). For suppose there exists a vertex w ∈ V 12 adjacent to some vertex w ∈ V 13 (resp. w ∈ V 24 ). But now w is adjacent to exactly three vertices of the cycle induced by v 1 , v 2 , v 3 , w (resp. v 1 , v 2 , v 4 , w ), a contradiction. Similarly if w, w ∈ V 13 (resp. w, w ∈ V 24 ) are adjacent, then w is adjacent to exactly three vertices of the cycle induced by v 1 , v 3 , v 4 , w (resp. v 2 , v 3 , v 4 , w ), a contradiction (see Claim 2). Finally we need to prove that no vertex in V 13 is adjacent to some vertex in V 24 . Suppose for a contradiction that w ∈ V 13 and w ∈ V 24 are adjacent. Then it follows from Lemma 4.11 that if we delete the edge ww there exists a stable set S in C 2 -ww containing w and w , and such that (C 2 -ww ) -V (S) is a split graph. But since v 1 , v 2 , v 3 , v 4 ∈ S, it follows that (C 2 -ww ) -V (S) contains C, a contradiction. Thus we conclude that V 12 ∪ V 34 ∪ V 13 ∪ V 24 induces a stable set. This implies that C 2 -v 2 v 3 is necessarily bipartite (indeed every trinagle in C 2 contains either v 2 or v 3 ), a contradiction. This proves Claim 3. So we may assume that there exists no vertex in V (C 2 ) which is adjacent to exactly two consecutive vertices of an induced cycle of length four in C 2 .

Claim 4 There exists no vertex v ∈ V (C 2 ) \ V (C) such that v is adjacent to exactly one vertex of V (C).

Suppose for a contradiction that there exists a vertex v ∈ V (C 2 ) \ V (C) such that v is adjacent to exactly one vertex of V (C), say v 1 . From Lemma 4.10 it follows that if we add the edge vv 3 there exists a clique K in C 2 + vv 3 containing v and v 3 , and such that (C 2 + vv 3 ) -V (K) is bipartite. We claim that |K| = 2. Indeed, assume there exists a vertex w adjacent to both v and v 3 . Clearly w = v 2 , v 4 . Furthermore w is non-adjacent to both v 2 and v 4 (see Claims 2 and 3). Thus v 1 , v 3 , v 4 , v, w induce a cycle of length five, a contradiction. Hence |K| = 2. We conclude that every induced odd cycle of length three in C 2 necessarily contains either v or v 3 . Since C 2 -v is not bipartite (otherwise G would be 2-split-colorable), there exist w 1 , w 2 such that v 3 , w 1 , w 2 induce a graph isomorphic to K 3 . Clearly w 1 , w 2 = v 2 , v 4 . But now it follows from Lemma 4.10 that if we add the edge vv 2 there exists a clique K in C 2 +vv 2 containing v and v 2 , and such that (C 2 + vv 2 ) -V (K) is bipartite. But clearly K does not contain any of v 3 , w 1 , w 2 . Thus (C 2 + vv 2 ) -V (K) contains a graph isomorphic to K 3 , a contradiction. This proves Claim 4. Thus there exists no vertex in C 2 that is adjacent to exactly one vertex of an induced cycle of length four.

The above Claims and the facts that C 2 is connected and not 2-split-colorable imply that there exists a vertex w ∈ V (C 2 ) \ V (C) which is adjacent to two non-consecutive vertices of V (C), say v 1 , v 3 . First assume that there exists a vertex w ∈ V (C 2 ) \ V (C) adjacent to v 2 , v 4 . Then we claim that w, w are adjacent. Indeed, if w, w are non-adjacent, then w is adjacent to exactly one vertex of the cycle induced by v 1 , v 2 , v 3 , w, contradicting Claim 4. Thus w, w are adjacent. Now by applying Lemma 4.11 to the edge ww we conclude that (C 2 -ww ) -V (S) is a split graph, where S is a stable set containing w, w . But (C 2 -ww ) -V (S) clearly contains C, a contradiction. So we may assume now that every vertex in V (C 2 ) \ V (C) must be adjacent to both v 1 and v 3 . Let w 1 , w 2 ∈ V (C 2 ) \ V (C). Then we claim that w 1 , w 2 are non-adjacent. Indeed, if they are adjacent, then w 1 is adjacent to three vertices of the 4-cycle induced by v 1 , w 2 , v 3 , v 4 , a contradiction (see Claim 2). Thus V (C 2 ) \ V (C) is a stable set. But now it follows that C 2 is bipartite, a contradiction. This proves the "only if" part.

Fig. 1 :

 1 Fig. 1: The graph G3,5.

Fig. 2 :

 2 Fig. 2: The five conditions in Proposition 3.2 are not sufficient.

  Proposition 4.3 Let G be a graph with no universal vertex and such that χ S (G + e) = χ S (G) -1 for any missing edge e in G. Then G is k-split-critical, where k = χ S (G). Proof: Let u, v be two non-adjacent vertices in G. Consider the missing edge e = vu. G-v is an induced subgraph of G + e, hence χ S (G -v) ≤ χ S (G + e) = χ S (G) -1. Since G has no universal vertex, this is true for every vertex v ∈ V (G).

Fig. 4 :

 4 Fig.4: A connected 3-split-critical graph where adding the dotted missing edge does not decrease χS.

  Proposition 4.7 A graph G is split-decreasing if and only if G is split-decreasing. Proof: This follows from the facts that χ S (G + e) = χ S (G) -1 = χ S (G) -1, and χ S (G + e) = χ S (G + e) = χ S (G -e). 2 Proposition 4.8 Let G = (V, E) be a graph with k connected components and χ S (G) = k, for k ≥ 2.

Fig. 5 :

 5 Fig. 5: (a) 3K2 and (b) C4 ∪ K2.

Acknowledgements

The authors would like to thank two anonymous referees for their careful reading of this paper and their comments which helped improving the paper considerably.

funded by the B.U. Research Fund, Grant 09A302P, whose support is greatly acknowledged. ‡ Research supported by the Centre for Discrete Mathematics and Its Applications (DIMAP), University of Warwick and by FNR grant TR-PDR BFR08-17.

Claim 1 There exists no center v of C.

Suppose for a contradiction that there exists a center v of C. We claim that all vertices in V (C 2 )\V (C) are non-adjacent to v. If not, then let w ∈ V (C 2 ) \ V (C) be adjacent to v. Then it follows from Lemma 4.11 that if we delete the edge vw there exists a stable set S in C 2 -vw containing v and w, and such that (C 2 -vw) -V (S) is a split graph. Since v is a center of C, it follows that v 1 , v 2 , v 3 , v 4 ∈ S. Thus (C 2 -vw) -V (S) contains C, a contradiction. So we may assume that all vertices in V (C 2 ) \ V (C) are non-adjacent to v. Next we claim that these vertices are centers of C. If not, then let w ∈ V (C 2 ) \ V (C) be non-adjacent to v i for some i ∈ {1, 2, 3, 4}, say v 1 . It follows from Lemma 4.10 that if we add the edge wv 1 there exists a clique K in C 2 + wv 1 containing w and v 1 , and such that (C 2 + wv 1 ) -V (K) is bipartite. Clearly K does not contain neither v nor v 3 , and K contains at most one vertex of v 2 , v 4 . Thus (C 2 + wv 1 ) -V (K) contains a graph isomorphic to K 3 , a contradiction. Hence all vertices in V (C 2 ) \ V (C) are centers of C. If there exists only one center, then G is clearly 2-split colorable, a contradiction. If there exist exactly two centers of C, then C 2 is isomorphic to 3K 2 , a contradiction. Thus we may assume that there exist at least three centers, say v, w, u. It follows from the above that v, w and u are pariwise non-adjacent. Now it follows from Lemma 4.10 that if we add the edge wu there exists a clique K in C 2 + wu containing w and u, and such that (C 2 + wu) -V (K) is bipartite. But clearly v ∈ V (K) and at most two adjacent vertices among v 1 , v 2 , v 3 , v 4 belong to K. Thus (C 2 + wu) -V (K) contains a graph isomorphic to K 3 , a contradiction. This proves Claim 1. So we conclude that there exists no vertex in V (C 2 ) which is a center of an induced cycle of length four in C 2 .

Claim 2 There exists no vertex v ∈ V (C 2 ) \ V (C) adjacent to exactly three vertices of V (C).

Suppose for a contradiction that there exists a vertex v ∈ V (C 2 ) \ V (C) adjacent to exactly three vertices of V (C), say v 1 , v 2 , v 3 . We claim that every vertex in V (C 2 ) \ (V (C) ∪ {v}) is adjacent to v 4 . If not, then let w ∈ V (C 2 ) \ (V (C) ∪ {v}) be non-adjacent to v 4 . It follows from Lemma 4.10 that if we add the edge wv 4 there exists a clique K in C 2 + wv 4 containing both w and v 4 , and such that (C 2 + wv 4 ) -V (K) is bipartite. K clearly does not contain neither v nor v 2 . Furthermore K contains at most one of the vertices v 1 , v 3 . Thus (C 2 + wv 4 ) -V (K) contains a graph isomorphic to K 3 , a contradiction. Now we claim that all vertices in V (C 2 ) \ (V (C) ∪ {v}) are non-adjacent to v. Indeed if there exists a vertex w ∈ V (C 2 ) \ (V (C) ∪ {v}) adjacent to v, then it follows from Lemma 4.11 that if we delete the edge vw there exists a stable set S in C 2 -vw containing v w, and such that

). It follows from Lemma 4.11 that if we delete the edge vv 1 (resp. vv 3 ) there exists a stable set

and suppose that w is adjacent to v 1 , v 4 (resp. v 3 , v 4 ). Then it follows from Lemma 4.10 that if we add the edge wv 3 (resp. wv 1 ) there exists a clique K in C 2 + wv 3 (resp. C 2 +wv 1 ) containing w and v 3 (resp. w, v 1 ), and such that (

Next suppose that some vertex w ∈ V (C 2 ) \ (V (C) ∪ {v}) is adjacent to v 2 , v 4 . It follows from Lemma 4.11 that if we delete the edge wv 2 there exists a stable set S in C 2 -wv 2 containing w and v 2 , and such that (C 2 -wv 2 ) -V (S) is a split graph. But clearly S does not contain vertices v 1 , v 3 , v 4 , v. Thus (C 2 -wv 2 ) -V (S) contains an induced cycle of length four, a contradiction. Now let w ∈ V (C 2 ) \ (V (C) ∪ {v}) be adjacent to v 4 and non-adjacent to v 1 , v 2 , v 3 , v. But then it follows from Lemma 4.10 that if we add the edge wv 1 there exists a clique K in C 2 + wv 1 containing w and v 1 , and such that (C 2 + wv 1 ) -V (K) is bipartite. But K does not contain any of the vertices v, v 2 , v 3 , and thus (C 2 + wv 1 ) -V (K) contains a graph isomorphic to K 3 , a contradiction.

From the above discussion, it follows that for every vertex w ∈ V (C 2 ) \ (V (C) ∪ {v}), w is adjacent to v 1 , v 3 , v 4 and non-adjacent to v, v 2 . If only one such vertex exists, then C 2 is isomorphic to C 4 ∪ K 2 , a contradiction. So we may assume that at least two such vertices exist, say w 1 , w 2 . First suppose that w 1 , w 2 are non-adjacent. Then it follows from Lemma 4.10 that if we add the edge w 1 w 2 there exists a clique K in C 2 + w 1 w 2 containing w 1 , w 2 and such that

contains a graph isomorphic to K 3 , a contradiction. Thus we may assume that w 1 , w 2 are adjacent. But now it follows from Lemma 4.11 that if we delete the edge w 1 w 2 there exists a stable set S in C 2 -w 1 w 2 containing w 1 and w 2 , and such that (C 2 -w 1 w 2 ) -V (S) is a split graph. Clearly v 1 , v 3 , v 4 ∈ V (S) and at most one of v, v 2 belongs to S. Thus C 2 -w 1 w 2 contains a cycle o four vertices, a contradiction.

We conclude V (C 2 ) \ (V (C) ∪ {v}) = ∅. But now G is clearly 2-split-colorable, a contradiction. This proves Claim 2. Thus we may assume that no vertex in V (C 2 ) is adjacent to exactly three vertices of an induced cycle of length four in C 2 .

Claim 3 There exists no vertex v ∈ V (C 2 ) \ V (C) adjacent to exactly two consecutive vertices in V (C).

Suppose for a contradiction that there exists a vertex v ∈ V (C 2 ) \ V (C) adjacent to exactly two consecutive vertices in V (C), say v 1 , v 2 . We claim that there exists no vertex w ∈ V (C 2 ) \ V (C) adjacent to v 1 , v 4 (resp. v 2 , v 3 ). Indeed if there exists a vertex w adjacent to v 1 , v 4 (resp. v 2 , v 3 ), then it follows from Lemma 4.10 that if we add the edge wv 3 (resp. wv 4 ) there exists a clique K in C 2 +wv 3 (resp. C 2 +wv 4 ) containing w and v 3 (resp. w and v 4 ), and such that (C 2 + wv 3 ) -V (K) (resp. (C 2 + wv 4 ) -V (K)) is bipartite. But K clearly does not contain any of the vertices v, v 1 , v 2 . Thus (C 2 + wv 3 ) -V (K) (resp. (C 2 + wv 4 ) -V (K)) contains a graph isomorphic to K 3 , a contradiction.

Furthermore we claim that every vertex w ∈ V (C 2 ) \ (V (C) ∪ {v}) is adjacent to exactly one vertex of v 2 , v 3 , and to exactly one vertex of v 1 , v 4 . Suppose there exists a vertex w ∈ V (C 2 ) \ (V (C) ∪ {v}) non-adjacent to v 1 , v 4 (resp. v 2 , v 3 ). Then it follows from Lemma 4.10 that if we add the edge wv 4 (resp. wv 3 ) there exists a clique K in C 2 + wv 4 (resp. C 2 + wv 3 ) containing w and v 4 (resp. w and v 3 ), and such that

Thus it follows that the vertices of V (C 2 ) \ V (C) can be partitioned into four sets V 12 , V 34 , V 13 , V 24 , where V ij is the set of vertices adjacent to v i , v j and non-adjacent to {v 1 , v 2 , v 3 , v 4 } \ {v i , v j }. We claim that V 12 ∪ V 34 ∪ V 13 ∪ V 24 induces a stable set. If not, then assume there exist w, w ∈ V 12 (resp. V 34 ) which are adjacent. From Lemma 4.11 it follows that if we delete the edge v 1 v 2 (resp. v 3 v 4 ) there exists a stable set S in C 2 -v 1 v 2 (resp. C 2 -v 3 v 4 ) containing v 1 and v 2 (resp. v 3 and v 4 ), and such that

Let us now prove the "if" part. First suppose that C 2 is isomorphic to 3K 2 . Then it follows immediately from Theorem 4.6 that G is split-decreasing by setting k = 3 and p = 2. So assume now that C 2 is isomorphic to

be the remaining vertices of C 2 with v being adjacent to v 1 , v 2 v 3 and v being adjacent to v 1 , v 3 , v 4 . Notice that v 1 v 3 is missing in G. Denote by x, y, z the vertices in C 1 . One can easily see that G is 3-split-colorable (take for instance three cliques C 1 , K 1 , K 2 , where K 1 is induced by v, v 1 , v 2 , and K 2 is induced by v , v 3 , v 4 ) but not 2-split-colorable.

Let us now show that G is split-decreasing. First we suppose that we add a missing edge. By symmetry we only have to consider the following cases. (1) If we add the edge vv , then

Finally let us suppose that we delete an edge. Again due to symmetry we only have to consider the following cases. (1) If we delete the edge xy, then (K, K ; {x, y}, {z}) is a 2-split-coloring where K is induced by v 1 , v 2 , v, and K is induced by v

(3) finally if we delete the edge vv 2 , then (C 1 , K; {v, v 2 }, {v 3 }) is a 2-split-coloring where K is induced by v 1 , v 4 , v . This proves Theorem 4.15. 2

Conclusion

We hope that this study will stimulate further research in this topic. For instance, one can try to find graphs for which the bounds in Proposition 4.1 hold with equality. Namely, what are the graphs for which the removal of the edge set of an induced C 4 or 2K 2 or C 5 decreases/increases the split-chromatic number exactly by one? The characterization of graphs with split-chromatic number two and such that the addition of any edge decreases the split-chromatic number (by one) is given in Corollary 4.4. One can try to characterize graphs with higher split-chromatic number and having the same property. Another interesting question is to consider the connectivity properties of uniquely split-colorable graphs. Lastly, we showed that a graph is split-decreasing with split-chromatic number three, and with two or three connected components if and only if it is isomorphic to 3K 3 , K 3 ∪ 3K 2 or K 3 ∪ (C 4 ∪ K 2 ). We leave as an open question the characterization of connected split-decreasing graphs with split-chromatic number three ; this would complete the characterization of split-decreasing graphs with split-chromatic number three.


Stefan Felsner
email: felsner@math.tu-berlin.de

Eric Fusy
email: fusy@lix.polytechnique.fr

Marc Noy
email: marc.noy@upc.edu

Éric Fusy

Asymptotic enumeration of orientations

Keywords: Orientation, Quadrangulation, Triangulation, D-finite generating function. To

Introduction

In a previous paper [START_REF] Felsner | Bijections for Baxter families and related objects[END_REF] we studied 2-orientations of quadrangulations and 3-orientations of triangulations from an enumerative point of view, focusing on bijections with other combinatorial objects, particularly trees and permutations. In this paper we focus on asymptotic counting.

A quadrangulation Q is a plane graph in which every face is a quadrangle. Since every face is bounded by an even circuit, a quadrangulation is bipartite; we always consider quadrangulations with a fixed 2coloring of the vertices. We distinguish two non-adjacent black vertices s and t on the outer face. An orientation of the edges of Q is a 2-orientation if every vertex, except s and t, has outdegree two. From the count of edges it follows that s and t are sinks in every 2-orientation.

Let q n be the number of 2-orientations among all quadrangulations with n inner faces. It is well known [START_REF] Fraysseix | Bipolar orientations revisited[END_REF] that q n also counts bipolar orientations on rooted planar maps with n edges (the root going from the source to the sink), which has been shown by R. Baxter (2) -using functional equations on generating functions-to satisfy the formula Using standard tools for estimating combinatorial sums we find in Theorem 1 that

q n = 1 n+1 1 n+1 2 n-1 r=0 n + 1 r n + 1 r + 1 n + 1 r + 2 .
q n ∼ 2 5 π √ 3 n -4 8 n ,
where a n ∼ b n means lim a n /b n = 1.

A quadrangulation is called prime if it has at least 3 inner faces and any of its 4-cycles is the boundary of a face. Accordingly, a 2-orientation of a prime quadrangulation is called a prime 2-orientation. The smallest prime quadrangulation is the cube, which has 5 inner faces, and has two distinct 2-orientations. Let p n be the number of prime 2-orientations with n inner faces; p n also counts bipolar orientations on rooted 3-connected maps with n edges (again the root going from the source to the sink). This follows from specializing the bijection between 2-orientations and bipolar orientations to prime quadrangulations (indeed rooted prime quadrangulations with n faces correspond to rooted 3-connected maps with n edges (14)).

(1, 2) ( The sequence (p n ) starts from n = 5 as 2, 0, 12, 24, 116, 418, 1722, . . .. We show in Theorem 2 that the number of prime 2-orientations is asymptotically

p n ∼ c • n -4 γ n ,
where ≈ 0.51 and γ ≈ 5.52 are constants (rounded to the digits shown) which can be computed analytically. For the proof we find first an equation linking the generating functions P (z) = p n z n and Q(z) = q n z n , which reflects the decomposition of arbitrary quadrangulations into prime quadrangulations.

Given the form of the q n , the series Q(z) is D-finite, that is, is the solution of a linear differential equation with polynomial coefficients. Using techniques from differential equations, we find the singular expansion of Q(z) near its dominant singularity 1/8 and then, using functional inversion, the singular expansion of P (z). Finally transfer theorems give the desired estimate.

We carry over the same program for 3-orientations. Consider a plane triangulation T , that is, a maximal plane graph, with n vertices and three special vertices a 1 , a 2 , a 3 in clockwise order around the outer face. An orientation of the inner edges of T is a 3-orientation if every inner vertex has outdegree three. From the count of edges it follows that the special vertices a i are sinks in every 3-orientation.

a 1 a 1 a 1 a 3 a 2 a 3 a 2 a 2 a 3
Fig. 3: Three triangulations and their 3-orientations.

The number t n of 3-orientations among all triangulations with n inner vertices was shown in (4) (see (3; 5) for alternative proofs) to be equal to c n+2 c n -c 2 n+1 , where c n = 1 n+1 2n n is a Catalan number. From this it follows easily, as shown in Theorem 3, that

t n ∼ 24 π n -5 16 n .
A 3-orientation is called prime if the underlying triangulation is 4-connected, that is, it has no separating triangle. Let s n be the number of prime 3-orientations. The sequence (s n ) starts from n = 1 as 1, 0, 2, 9, 57, . . .. We show in Theorem 4 that the number of prime 3-orientations is asymptotically

s n ∼ c • n -5 γ n ,
where in this case c ≈ 2.60 and γ ≈ 13.71. The proof is again based on a functional equation between T (z) = t n z n and S(z) = s n z m , and on singular expansions and transfer theorems for D-finite functions.

The following table summarizes the results in this paper. It is worth noticing that the subexponential order for the enumeration of structured maps (rooted maps endowed with a specific combinatorial structure, such as an orientation or a spanning tree) is not universal, being n -4 for 2-orientations and n -5 for 3-orientations (another example is the subexponential term n -3 for the enumeration of rooted maps endowed with a spanning tree ( 13)). This is in contrast to the asymptotic enumeration of rooted maps, where the subexponential order n -5/2 occurs systematically (see, for instance, (1)).

Class of orientations

For more general classes of orientations and related problems, we direct the reader to (6).

Preliminaries

To obtain asymptotic estimates we take advantage of the framework of Analytic Combinatorics, as developed in the book by Flajolet and Sedgewick [START_REF] Flajolet | Analytic combinatorics[END_REF]. Singularity analysis makes it possible to estimate the coefficients f n from the behavior of the generating function

f (z) = n f n z n
at its dominant singularity. We recall that a dominant singularity is one of smallest modulus. By Pringsheim's theorem, the radius of convergence ρ > 0 is always a dominant singularity [START_REF] Flajolet | Analytic combinatorics[END_REF]. More precisely, assume that f (z) is analytically continuable to a so-called ∆-domain for ρ, of the form

Ω = {|z| < ρ(1 + δ), Arg(z -ρ) ∈ [φ, 2π -φ]},
for some δ > 0 and 0 < φ < π/2. Then the following transfer rules hold, where Γ(x) is Euler's gamma function.

Transfer rules. For α / ∈ Z ≥0 and r ∈ Z ≥0 we have

f (z) ∼ z→ρ (1 -z/ρ) α ⇒ f n ∼ n→∞ 1 Γ(-α) n -α-1 ρ -n , (1)
f (z) ∼ z→ρ (z/ρ -1) r log(z/ρ -1) ⇒ f n ∼ n→∞ r!n -r-1 ρ -n . (2)
Thus if we can show that f (z) in a ∆-domain at its dominant singularity behaves like the left-hand side of one of the transfer rules, then we get a precise estimate for its coefficients.

The transfer rules also apply when there are finitely many singularities ζ 1 , . . . , ζ on the boundary of the disk of convergence, provided analytic continuation holds in a ∆-domain of the form ζ i • Ω around each singularity. The contribution of each singularity is given by the transfer rules (with ρ replaced by ζ i ) and the asymptotics for f n is obtained by adding up the contributions of all singularities. As we are going to see, one of the problems we have to face is to rule out the possibility of other singularities besides the obvious one.

We also need some elements of the theory of linear differential equations in the complex plane. Our basic reference in this topic is the classical book by Ince [START_REF] Ince | Ordinary differential equation[END_REF] (see [START_REF] Henrici | Applied and Computational Complex Analysis[END_REF] for a more modern treatment). Let

p 0 (z) d n f (z) z n + p 1 (z) d n-1 f (z) z n-1 + • • • + p n-1 (z) df (z) dz + p n (z)f (z) = 0, (3)
be a homogeneous linear differential equation whose coefficients p i (z) are polynomials in z. Then the only finite singularities of a solution f (z) which can occur are the zeroes of the leading coefficient p 0 (z); notice in particular that there are no movable singularities, that is, singularities which depend on the initial conditions. Let S be the set of zeroes of p 0 (z). Then the analytic solutions of (3) in the neighbourhood of any point of C\S form a vector space of dimension n over C. This implies that any solution of ( 3) is analytically continuable along any path avoiding S.

The analytic theory of linear differential equations further extends to deal with singularities. However in this case one has to add further restrictions. If one wishes that the solution through a singular point is well behaved, one has to impose the condition of the singular point being regular. A necessary and sufficient condition for regularity is the following. Rewrite (3) as

d n f (z) z n + P 1 (z) d n-1 f (z) z n-1 + • • • + P n-1 (z) df (z) dz + P n (z)f (z) = 0, (4)
where the P i are now rational functions. A singular point z 0 is regular if

P i = O((z -z 0 ) -i ), for i = 1, . . . , n.
That is, P i has a pole at z 0 of order at most i. The terminology does not mean that the solution is analytic, but refers to the fact that the possible divergence at the singularity is at most polynomial. If z 0 is a regular singularity, then it can be shown that there exists a basis of solutions B 1 (z), . . . , B n (z) that are linear combinations of elements of the the form

Z µ (log Z) k s(Z),
where Z = z -z 0 and s(Z) is analytic at zero, and the µ are complex numbers. Hence the solutions are analytic in a slit domain {|Z| < δ}\{Z ≥ 0}. Moreover, the B i (z) have singular expansions at z 0 that are explicitly computable [START_REF] Ince | Ordinary differential equation[END_REF]Chap.16).

We summarize the previous discussion as follows.

Lemma 1 A sufficient condition for a singular point z 0 of Equation ( 3) to be regular is that

P i = O((z - z 0 ) -i
), for i = 1, . . . , n. In this case there exists a basis of solutions that are linear combinations of elements of the form Z µ (log Z) k s(Z), where Z = z -z 0 and s(Z) is analytic at zero.

Counting two-orientations

Let q n be the number of 2-orientations on quadrangulations with n inner faces, which satisfies (2)

q n = 1 n+1 1 n+1 2 n-1 r=0 n + 1 r n + 1 r + 1 n + 1 r + 2 .
This expression is a sum involving binomial coefficients, and there are well established techniques for estimating this kind of sums [START_REF] Odlyzko | Asymptotic enumeration methods[END_REF].

Theorem 1 (asymptotic number of 2-orientations) The number q n of 2-orientations on quadrangulations with n inner faces satisfies asymptotically

q n ∼ 2 5 π √ 3 n -4 8 n . (5
(n, r max + r) = (2/π) 3/2 8 n n -3/2 exp(-6r 2 /n)(1 + O(1/n)) uniformly for r ≤ n 2/3 .
3. Select a window to focus on, and prove that the summand is negligible outside the window. We find b(n, r max + r) = O(8 n exp(-6n 1/3 )) uniformly for |r| ≥ n 2/3 , so that the sum outside the window |r -r max | ≤ n 2/3 is negligible in front of b(n, r max ).

4. Show that the sum in the window converges to an integral. We find

n 2/3 r=-n 2/3 b(n, r max + r) ∼ (2/π) 3/2 8 n n -3/2 n 2/3 r=-n 2/3 exp(-6r 2 /n) ∼ (2/π) 3/2 8 n n -3/2 √ n R exp(-6x 2 )dx .
Since the integral equals π/6, we finally obtain r b(n, r) ∼ 2/(π √ 3)8 n n -1 . This yields the estimate of q n as claimed, since

q n ∼ 2n -3 r b(n + 1, r). 2
Recall that a 2-orientation is called prime if the underlying quadrangulation has at least 3 inner faces and has no separating quadrangle. Our aim is to find an asymptotic estimate for p n .

The asymptotic number of prime 2-orientations is obtained by singularity analysis of the corresponding generating function. Here is an outline of the strategy we follow:

1. Find an equation relating the generating function Q(z) = n q n z n for 2-orientations and the generating function P (w) = n p n w n for prime 2-orientations, counted with respect to the number of inner faces (Lemma 2).

2. Find the singular expansion of Q(z) at the dominant singularity 1/8 (Lemma 3), using both the property that Q(z) is D-finite (solution of a linear differential equation with polynomial coefficients) and the asymptotic estimate of q n = [z n ]Q(z), obtained in Theorem 1.

3. From the singular expansion of Q(z) and the equation relating Q(z) and P (w), determine the dominant singularity ρ of P (w), and the singular expansion of P (w) at ρ (Lemma 4). And show that ρ is the unique singularity of P (w) on the disk {w; |w| = ρ} (Lemma 5).

4. Using the transfer rules, translate the singular expansion of P (w) to an asymptotic estimate of the coefficients p n (Theorem 2).

All calculations have been done with the help of the computer algebra system Maple [START_REF] Maplesoft | [END_REF]. The package DETOOLS has been particularly helpful to deal with the singularity analysis of D-finite series.

Lemma 2 Let Q(z) = n q n z n and P (w) = n p n w n be the series counting respectively 2-orientations and prime 2-orientations with respect to the number of inner faces. Then

Q(z) = z + 2Q(z) 2 1 + Q(z) + P (Q(z)). (6)
Proof: We rely on a well-known decomposition of a quadrangulation into prime components ( 14), reformulated here for 2-orientations. First, define a diagonal of a quadrangulation Q as a path of two inner edges connecting two opposite outer vertices of Q. A quadrangulation is said to be black-diagonal if it has a diagonal connecting the two outer black vertices. Let D(z) = n d n z n be the series counting black-diagonal 2-orientations with respect to the number of inner faces. To construct a black-diagonal 2-orientation in a unambiguous way, take a quadrangle Q and draw k ≥ 1 diagonals connecting the pair of black vertices of Q. Then insert k + 1 non black-diagonal 2-orientations in the slots created by the k diagonals. This construction yields

D(z) = k≥1 (Q(z) -D(z)) k+1 = (Q(z) -D(z)) 2 1 -(Q(z) -D(z)) , so that D(z) = Q(z) 2 /(1 + Q(z)).
Next, define a non-diagonal quadrangulation as a quadrangulation having no diagonal, and define a non-diagonal 2-orientation as a 2-orientation of a non-diagonal quadrangulation. A non-diagonal 2-orientation with at least two inner faces is obtained from a prime 2-orientation by substituting every inner quadrangle (necessarily a face) by an arbitrary 2-orientation: this gives the term P (Q(z)), since substitution of combinatorial objects corresponds to substitution in generating functions (we are using throughout the symbolic approach for working with generating functions, as in ( 7)). The expression (6) for Q(z) is simply obtained by summing the possible cases: the first term stands for the 2-orientation with no inner vertex, the second term for diagonal 2-orientations, and the third term for non-diagonal 2-orientations with at least two inner faces. 2

Lemma 3 (singular behavior of Q(z)) The series Q(z) is analytically continuable to the whole complex plane slit by the half-lines z ≥ 1/8 and z ≤ -1, and has the following singular expansion as z tends to

1/8, Q(z) = Z 3 log(Z)α(Z) + β(Z) with Z = z -1/8, (7)
where α(Z) and β(Z) are analytic at 0 and their expansions start as

α(Z) = 2 13 /(3 3/2 π) + O(Z), β(Z) = Q(1/8) + Q (1/8)Z + O(Z 2 ).
Proof: First, it is easy to show that q n is P -recursive, that is, satisfies a linear recurrence with polynomial coefficients. Indeed q n is obtained from binomial coefficients using operators (sum, termwise product, . . . ) that are well-known to keep the property of P -recursiveness, see (7, App. B.4). It turns out that the q n satisfy a second-order linear recurrence:

(n + 3) (n + 2) q n -7 n 2 + 7 n -2 q n-1 -8 (n -1) (n -2) q n-2 = 0.
Multiplying by z n and summing over n, the previous equation translates to the following differential equation satisfied by

Q(z) = n q n z n : -8 z 4 -7 z 3 + z 2 d 2 dz 2 f (z) + -16 z 3 -28 z 2 + 6 z d dz f (z) + (-12 z + 6) f (z) -12 z = 0.
Remark. The recurrence was computed using the function sumrecursion from the Maple package sumtools; it is also listed in entry A00181 from the On-Line Encyclopedia of Integer Sequences. The differential equation is obtained using the function rectodiffeq from the Maple package gfun.

As mentioned in Section 2, we need a homogenous equation normalized in d 3 f /dz 3 . This is achieved upon replacing the left-hand side L(z) of the previous equation by zL (z) -L(z), and normalizing. The result is

d 3 dz 3 f (z) + 40 z 2 + 42 z -7 z(z + 1)(8z -1) d 2 dz 2 f (z) + 32z 2 + 40z -6 z 2 (z + 1)(8z -1) d dz f (z) + 6 z 3 (z + 1)(8z -1) f (z) = 0. ( 8
)
The singularities of the coefficients (poles) are in S := {0, -1, 1/8}. As discussed earlier the analytic solutions of (8) in the neighbourhood of any point of C\S form a vector space of dimension 3 over C. This implies that any solution of ( 8) is analytically continuable along any path avoiding S. In particular, the solution Q(z) = n q n z n , which is clearly analytic at 0, is continuable to the whole complex plane slit by the half-lines z ≥ 1/8 and z ≤ -1. This is a ∆-domain for the dominant singularity 1/8, hence transfer theorems will apply.

For i ∈ {1, 2, 3}, the coefficient for the derivative of order 3 -i in ( 8) is O((8z -1) -i ) , so that 1/8 is a regular singularity. Hence there exists a basis of solutions B 1 (z), B 2 (z), B 3 (z) of ( 8) that are analytic in a slit domain {|Z| < δ}\{Z ≥ 0}, where we set Z = z -1/8. Moreover, singular expansions at 1/8 of the basis functions are explicitly computable.

All calculations done, we find that two of the basis solutions are analytic and the third one has a (convergent) singular expansion of the form f (Z)Z 3 log(Z) + g(Z) for some functions f (Z) and g(Z) analytic at 0. Therefore, as a linear combination of the basis solutions, Q(z) has also a singular expansion of the form

Q(z) = log(Z) k≥3 a k Z k + k≥0 b k Z k , with Z = z -1/8, holding in a slit neighborhood of 1/8. Notice that b 0 = Q(1/8) and b 1 = Q (1/8).
Remark. The basis solutions are computed using the function formal sol from the Maple package DEtools. At first sight it appears that only one of the solutions is analytic, but the two solutions containing logarithmic terms can be combined into a second analytic solution.

Let us look at the singular part. Clearly Q(z) is singular at 1/8, otherwise the growth rate of q n would be larger than 8, and Theorem 1 shows that it is equal to 8. Hence there exists a smallest integer k ≥ 3 such that a k = 0. According to the transfer rule (2),

q n ∼ n→∞ a k k!8 -k n -k-1 8 n .
Comparing with the asymptotics of q n obtained in Theorem 1, we obtain k = 3 and a 3 = 2 13 /(3 3/2 π). This concludes the proof.

2

Lemma 4 (singular expansion of P (w)) The generating function P (w) = n p n w n counting prime 2orientations has radius of convergence ρ = Q(1/8) ≈ 0.18, and the leading singular term of

P (w) at ρ is C(w -ρ) 3 log(w -ρ), where C = 2 13 /(Q (1/8) 4 3 3/2 π),
holding in a "∆-neighborhood" for ρ, of the form

{|w -ρ| < δ , Arg(w -ρ) ∈ [φ, 2π -φ]},
with δ > 0 and φ < π/2.

Proof: Let F (w) be the inverse function of Q(z). Setting w = Q(z) in Equation ( 6), we get

P (w) = w -2w 2 /(1 + w) -F (w).
Since Q(1/8) < 1 and the only singularity of 2w 2 /(1 + w) is at w = -1, the radius of convergence ρ of P (w) is the same as that of F (w). Since the series Q(z) has positive coefficients, it defines an increasing function. It follows that the radius of convergence of the inverse

F (w) is ρ = Q(1/8) < +∞.
The singular expansion of F (w) at ρ is obtained iteratively from the one of its inverse Q(z) at 1/8, given by Equation [START_REF] Flajolet | Analytic combinatorics[END_REF], using first w -ρ ∼ Q (1/8) • (z -1/8) and then repeatedly bootstrapping. The leading singular term λ(z -1/8) 3 log(z -1/8) of Q(z), with λ = 2 13 /(3 3/2 π), yields a term

-λ/Q (1/8) 4 (w -ρ) 3 log(w -ρ)
in the expansion of P (w), which is the leading singular term.

Moreover, the singular expansion of P (w) at ρ holds in a neighborhood Ω of ρ, where Ω is the image of a slit neighborhood {|z -1/8| < δ}\{z ≥ 1/8}, with δ > 0. Since ρ (w) converges to a positive constant at w = ρ, it is locally conformal at ρ. Hence Ω contains a "∆-neighborhood" for ρ, of the form {|w -ρ| < δ , Arg(w -ρ) ∈ [φ, 2π -φ]}, with δ > 0 and φ < π/2. Finally, since ρ is the smallest positive singularity of P (w), Pringsheim's theorem ensures that ρ is the radius of convergence of P (w).

2

Lemma 5 (uniqueness of dominant singularity of P (w)) The series P (w) has no singularity other from ρ on the closed disk {w; |w| ≤ ρ}, that is, P (w) is analytically continuable around any w = ρ with |w| ≤ ρ.

Proof: First, since ρ is the radius of convergence of P (w), P (w) is analytic on the open disk {w; |w| < ρ}.

Recall that Q(z) and Q (z) converge at 1/8, since the coefficients of Q(z) are asymptotically equivalent to cn -4 8 n . In addition, as we have seen

Q(1/8) is equal to ρ. Since F (Q(z)) = z, we have F (Q(z))Q (z) = 1, so F (ρ) = 1/Q (ρ) and P (ρ) = 1 -4ρ/(1 + ρ) + 2ρ 2 /(1 + ρ) 2 -F (ρ).
In other words P (ρ) is finite, which ensures that P (w) (and similarly P (w)) is absolutely convergent on the closed disk {w; |w| ≤ ρ}. We claim that, for w 0 ∈ C(0, ρ)\{ρ}, Q is analytic at z 0 := F (w 0 ), i.e., z 0 is not in S := {-1, 1/8}. The case z 0 = -1 is excluded easily. Indeed

|F (w)| = |w(1 -w)/(1 + w) -P (w)| ≤ |w(1 -w)/(1 + w)| + |P (w)|,
hence for |w| = ρ (and using the fact that P (w) has nonnegative coefficients),

|F (w)| ≤ ρ 1 + ρ 1 -ρ + P (ρ) ≈ 0.1873 + 0.0006 < 1, computing P (ρ) as ρ(1 -ρ)/(1 + ρ) -F (ρ) = ρ(1 -ρ)/(1 + ρ) -1/8. Excluding z 0 = 1/
> ρ(1 -ρ) 1 + ρ -P (ρ) = F (ρ) = 1/8,
that is, |z| > 1/8. Hence Q(z) is analytic at z 0 . Now, take a path P w0 from 0 to w 0 that avoids the preimages (for Q(z)) of the singularities {-1, 1/8}; and let Q z0 be the image of P w0 by P (w). Since Q z0 avoids its singularities, Q(z) is analytically continuable along Q z0 . In addition, all along P w0 , there holds the equation Q(P (w)) = w. Hence P (w) is the local inverse of Q(z) all along the path P w0 . In particular Q(z) is the local inverse of P (w) at the end of the path, i.e., at the point w 0 . Since Q(z) is analytic at z 0 = P (w 0 ), we conclude that P (w) is analytic around w 0 .

2

From the singular expansion of P (w), the transfer rule (2) yields directly the following asymptotic estimate for the number of prime 2-orientations.

Theorem 2 (asymptotic number of prime 2-orientations) Let p n be the number of prime 2-orientations with n inner quadrangles. Then

p n ∼ c • n -4 γ n , (9)
where c = Q(1/8) 3 2 14 /(Q (1/8) 4 √ 3π) ≈ 0.5097001 and γ = Q(1/8) -1 ≈ 5.5195689.

Counting three-orientations

We now focus on the enumeration of 3-orientations (equivalently, of Schnyder woods) on triangulations.

Recall that the number of 3-orientations with n inner vertices is c n+2 c n -c 2 n+1 , where c n = 1 n+1 2n n is a Catalan number.

Theorem 3 (asymtotic number of 3-orientations) Let t n denote the number of 3-orientations with a fixed outer triangle and n inner vertices. Then

t n ∼ 24 π n -5 16 n . (10)
Proof: From the formula above we get t n = 6(2n)!(2n + 2)!/(n!(n + 1)!(n + 2)!(n + 3)!). Applying Stirling's estimate, the estimate for t n follows easily. 2

Our study continues with the asymptotic enumeration of so-called prime 3-orientations, which play a similar role for 3-orientations as prime 2-orientations for 2-orientations. Precisely, a prime triangulation is defined as a triangulation with at least one inner vertex and where each 3-cycle delimits a face (these are called simple by Tutte [START_REF] Tutte | A census of planar triangulations[END_REF] and correspond exactly to the triangulations that are 4-connected); and a prime 3-orientation is a 3-orientation on a prime triangulation. The first prime triangulation is the tetrahedron, with has 4 vertices. As in Section 3, we aim at finding an asymptotic estimate for the number s n of prime 3-orientations with n inner vertices. (The coefficients s n start from n = 1 as 1, 0, 2, 9, 57, 400, 3066.)

Our study follows the same lines as for prime 2-orientations, except that we have to deal with two dominant singularities (instead of a unique one for prime 2-orientations) when analyzing the generating functions counting 3-orientations and prime 3-orientations.

Lemma 6 Let T (z) = n t n z 2n+1 and S(w) = s n w 2n+1 be the series counting respectively 3orientations and prime 3-orientations with respect to the number of inner faces (due to Euler relation, the number of inner faces is of the form 2n + 1, with n the number of inner vertices). Then T (z) = z + S(T (z)).

(11)

Proof: A 3-orientation with at least one inner vertex is obtained from a prime 3-orientation by substituting every inner face by an arbitrary 3-orientation: this gives the term P (T (z)), while the term z takes account of the empty triangle. This is a classical approach introduced by Tutte (16). 2

Lemma 7 (singular behavior of T (z)) The generating function T (z) has two dominant singularities: 1/4 and -1/4. In addition, T (z) is analytically continuable to the whole complex plane slit by the two half-lines z ≥ 1/4 and z ≤ -1/4; and the following singular expansions hold at ±1/4:

T (z) = ±(Z 4 log(Z)S 1 (Z) + S 2 (Z)), with Z = ±z -1/4, (12)
where S 1 (Z) and S 2 (Z) are analytic at 0 and their expansions start as From the transfer rule (2) applied to S(w) (there are two dominant singularities ±ρ, whose contributions are added up), we obtain the following asymptotic estimate for s n = [w 2n+1 ]S(w).

Theorem 4 (asymptotic number of prime 3-orientations) Let s n be the number of prime 3-orientations with n inner vertices. Then

s n ∼ c • n -5 γ n , (14)
where c = 3 • 2 9 • T (1/4) 3 /(T (1/4) 5 π) ≈ 2.5976882 and γ = T (1/4) -2 ≈ 13.7128393.

Fig. 1 :

 1 Fig. 1: Two quadrangulations and their 2-orientations.

Fig. 2 :

 2 Fig. 2: All prime quadrangulations with 5, 7 and 8 inner faces. A pair (a, b) below a quadrangulation Q indicates that Q allows a non-isomorphic choices of s, t on the outer face and it has b 2-orientations for each choice. This yields p5 = 2, p7 = 12 and p8 = 24.

)

  Proof: Let b(n, r) := n r n r+1 n r+2 . The asymptotic study of a sum such as r b(n, r) is classically done in four steps. 1. Locate the index r max of the largest summand b(n, r); in our case r max = n/2 up to shifting by one or two. 2. Compute the asymptotics of b(n, r) around r max . Using Stirling's formula we find b

8

 8 requires a bit more care. Notice that the function |w -2w 2 /(1 + w)| = |w||(1 -w)/(1 + w)| has its unique minimum on C(0, ρ) at ρ, and |P (w)| has its unique maximum on C(0, ρ) at ρ. Therefore, for w ∈ C(0, ρ)\{ρ}, |z| = |F (w)| = |w(1 -w)/(1 + w) -P (w)| ≥ |w(1 -w)/(1 + w)| -|P (w)|

S 1 (

 1 Z), S 2 (Z) = T (1/4) + T (1/4)Z + O(Z 2 ).

Acknowledgements

The authors thank Philippe Flajolet for a very helpful discussion on the asymptotics of D-finite series.

Proof: We set t(y) := n t n y n , so that T (z) = zt(z 2 ). Hence singularities and singular expansions of T (z) are directly obtained from those of t(y). the study of t(y) is completely similar to the one of the generating function Q(z) counting 2-orientations. First we observe that t n /t n-1 = 4(4n 2 -1)/((n + 3)(n + 2)), so that t n is P-recursive (of order 1). The recurrence turns to a linear differential equation satisfied by t(y), which reduces to the homogenous equation

The only poles are 0 and 1/16. As a solution of (13), t(y), which is clearly analytic at 0, is analytically continuable along any path avoiding 1/16, in particular t(y) is continuable to the complex plane slit by z ≥ 1/16. The singularity analysis of t(y) is done in a completely similar way as for Q(z) (Lemma 3). We find that two of the basis solutions of ( 13) are analytic at 1/16 and the third one admits a singular expansion of the form α(Z)Z 4 log(Z) + β(Z) for some analytic functions α(Z) and β(Z). Therefore, t(z) has also a singular expansion of the form

). According to the transfer rules 2, compared with the asymptotic of t n obtained in Theorem 1, we obtain a 4 = 1/π. The singularities and singular expansions of T (z) immediately follow, as

Lemma 8 (singular behavior of S(w)) The generating function S(w) = n s n w 2n+1 has two dominant singularities at ±ρ, with ρ = T (1/4), and is analytically continuable to a domain of the form {|z| < ρ(1 + δ), Arg(z -1/4) ∈ [φ, 2π -φ], Arg(-z -1/4) ∈ [φ, 2π -φ]} (∆-domain with two singularities), for some δ > 0 and φ ∈ (0, π/2). The leading singular terms of S(w) at ±ρ is ±C • W 4 log(W ), with W = ±w-ρ and C = 1/(2 6 πT (1/4) 5 ).

Proof: According to Equation [START_REF] Ince | Ordinary differential equation[END_REF], the functional inverse U (w) of T (z) satisfies U (w) = w -S(w). Hence the radius of convergence ρ of S(w) is the same as that of U (w). Since U (w) is the inverse of an increasing function T (z), it follows that ρ = T (1/4). The singular expansion of U (w) at ρ is easily obtained from that of T (z) at 1/4: the leading singular term λ(z -1/4) 4 log(z -1/4) of T (z), with λ = 1/(2 6 π), yields a term -λT (1/4) -5 (w -ρ) 4 log(w -ρ) in the singular expansion of U (w), which is the leading singular term. As argumented in the proof of Lemma 4, the singular expansion of U (w) at ρ holds in a "∆-neighborhood" of ρ. As U (w) = -U (-w), the singular expansion of U at -ρ is the opposite of the one at ρ, and holds in a ∆-neighborhood of -ρ. It remains to show that S(w) is analytic on C(0, ρ)\{±ρ}. We proceed similarly as in Lemma 5. First we check that, for w 0 ∈ C(0, ρ)\{±ρ}, the function T (z) is analytic at z 0 := U (w 0 ), i.e., z 0 = ±1/4; this follows from |z 0 | = |w 0 -S(w 0 )| ≥ |w 0 | -|S(w 0 )| > ρ -S(ρ) = 1/4, so z 0 = ±1/4. Finally, by the same arguments as in Lemma 5, we prove that T (z) is the local inverse of S(w) around w 0 .