Piotr Borowiecki

Dariusz Dereniowski

On-line Ranking of Split Graphs

Keywords: graph coloring, graph ranking, on-line algorithm, greedy algorithm, semi on-line algorithm, advice complexity, split graph

A vertex ranking of a graph G is an assignment of positive integers (colors) to the vertices of G such that each path connecting two vertices of the same color contains a vertex of a higher color. Our main goal is to find a vertex ranking using as few colors as possible. Considering on-line algorithms for vertex ranking of split graphs, we prove that the worst case ratio of the number of colors used by any on-line ranking algorithm and the number of colors used in an optimal off-line solution may be arbitrarily large. This negative result motivates us to investigate semi on-line algorithms, where a split graph is presented on-line but its clique number is given in advance. We prove that there does not exist a (2 -ε)-competitive semi on-line algorithm of this type. Finally, a 2-competitive semi on-line algorithm is given.

Introduction

In this paper we consider the vertex ranking problem for simple, finite, undirected graphs G = (V, E) with the vertex set V , edge set E and order n = |V (G)|. A coloring of a graph G = (V, E) is a function c : V (G) → Z + such that for each uv ∈ E(G) we have c(u) = c(v). Moreover, if each path between two vertices of the same color q contains a vertex of color greater than q, then c is a ranking of G. A ranking that uses k colors is called a k-ranking and the smallest k for which there exists a k-ranking of G, denoted by χ r (G), is the ranking number of G. See also [START_REF] Dereniowski | Rank coloring of graphs[END_REF] for a survey on graph rankings.

In what follows we use the standard graph theoretical notation and terminology. In particular, given U ⊆ V (G), G[U ] denotes the subgraph of G induced by U with vertex set U and edge set

E(G[U ]) = {uv ∈ E(G) | u, v ∈ U }. If H is an induced subgraph of G, it is customary to write H ≤ G, while H ≃ G is used when H is isomorphic to G. The complement G of a graph G is the graph with V (G) = V (G) and E(G) = {uv | uv / ∈ E(G)}. For v ∈ V (G), N G (v) = {u ∈ V (G) | uv ∈ E(G)} is the neighborhood of v in G, while N G [v] = N G (v) ∪ {v} is called the closed neighborhood of v in G.
A set of vertices I, I ⊆ V (G), is independent in G, if no two vertices of I are adjacent. The cardinality of a maximum independent set in G is called the independence number of a graph G, denoted by α(G). We use the symbol N r , r ≥ 0, to denote the edgeless graph of order r. A subgraph isomorphic to a complete graph K r is called a clique. The order of the largest clique in G is called the clique number of G, denoted by ω(G). We use H ∪ G for the union of vertex disjoint graphs H and G, while 2H denotes the graph consisting of two vertex disjoint copies of H. For any other notions undefined here we refer the reader to [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF][START_REF]Graph Colorings[END_REF][START_REF] West | Introduction to Graph Theory[END_REF].

The on-line version of the ranking problem is frequently viewed as a game between two players, Presenter (the adversary) and Painter (the coloring algorithm). In contrast to the off-line approach, Painter does not know the structure of the graph G = (V, E) that has to be colored. Presenter starts the game and reveals subsequent vertices of G in some order (v 1 , . . . , v n ) unknown to Painter. More precisely, each vertex v i is presented together with the edges E i = {v i v j ∈ E(G) | j < i}. Consequently, after presentation of v i , Painter knows only the structure of the subgraph G i induced by {v 1 , . . . , v i }. Painter has to irrevocably assign a permissible color c(v i ) to the vertex v i before v i+1 is presented. The aim of Painter is to use as few colors as possible while Presenter aims at finding an ordering of the vertices forcing Painter to use as many colors as possible. The game can also be viewed as a sequence (P 1 , A 1 , . . . , P n , A n ) of alternate moves P i = (v i , E i ) of Presenter and moves A i of the ranking algorithm. Defining a pair R i = (P i , A i ) as the i-th round we will also view the game as a sequence of n rounds (R 1 , . . . , R n ). In what follows we use χ A (G, π) to denote the number of colors used by the coloring algorithm A for the ordering π of the vertex set, and χ A (G) for the maximum number of colors that may be required by A to color G, i.e., χ A (G) = max π χ A (G, π). The on-line ranking number of a graph G is the minimum χ A (G) taken over all on-line ranking algorithms A. We say that an on-line ranking algorithm is c-competitive if there exists a constant b such that χ A (G) ≤ c • χ r (G) + b. We say for brevity that an algorithm is constant competitive if it is c-competitive for some constant c. We refer the reader interested in a more extensive description of a classical on-line coloring to [START_REF] Borowiecki | On-line coloring of graphs[END_REF][START_REF] Kierstead | Coloring Graphs On-line[END_REF].

Several results concerning on-line vertex ranking are known. Schiermeyer et al. [START_REF] Schiermeyer | On-line rankings of graphs[END_REF] characterized graphs with the on-line vertex ranking number equal to 3 and proved that the greedy algorithm, which always assigns the smallest permissible color to the incoming vertex, produces a (3 log 2 n)-ranking for a path P n . Note that χ r (P n ) = 1 + ⌊log 2 n⌋. On-line rankings of paths and cycles were also considered by Bruoth and Horňák [START_REF] Bruoth | On-line ranking number for cycles and paths[END_REF], who proved an even better bound of 2⌊log 2 n⌋ + 1 for both classes of graphs. This, in particular, implies that the ratio of the on-line and the off-line ranking numbers for paths is bounded by 2. The lower bound of 1.619 log 2 n-1 for the on-line ranking number of paths was given by the same authors in [START_REF] Bruoth | A lower bound for on-line ranking number of a path[END_REF]. It was also proved by Semanišin and Soták [START_REF] Semanišin | A note on on-line ranking number of graphs[END_REF] that there exists an infinite sequence of graphs for which the ratio of the on-line and the off-line ranking numbers can be arbitrarily large. Ghoshal et al. [START_REF] Ghoshal | Minimal rankings[END_REF] introduced the problem of finding a minimal ranking which is defined as a ranking with the property that decreasing the color assigned to any vertex results in a function that is not a ranking. The arank number of a graph G is the largest k such that there exists a minimal k-ranking of G. As pointed out by Isaak et al. [START_REF] Isaak | Greedy rankings and arank numbers[END_REF] there is a connection between on-line rankings and minimal rankings. In particular, the arank number equals the number of colors assigned in the worst case by the greedy ranking algorithm. So, the number of colors assigned by the greedy on-line algorithm is at most the arank number of the input graph. Ranking is also closely related to parity coloring (see, e.g., [START_REF] Borowiecki | Parity vertex colouring of graphs[END_REF][START_REF] Bunde | Parity and strong parity edge-colorings of graphs[END_REF]) and conflict-free coloring [START_REF] Even | Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks[END_REF]. A parity coloring is a coloring with the property that every path contains some color an odd number of times, while in a conflict-free coloring every path has to use some color exactly once.

In this paper we investigate the on-line version of the ranking problem for split graphs. A graph G is called a split graph if there exists a bipartition (C, I) of its vertex set such that I is an independent set and C induces a clique. Such a partition is called a split bipartition. Notice that a split bipartition does not have to be unique but it always satisfies one of the three conditions given in the following theorem.

(a) |I| = α(G) and |C| = ω(G), (b) |I| = α(G) and |C| = ω(G) -1, (c) |I| = α(G) -1 and |C| = ω(G).
We say that G is a split graph of type A if V (G) has a split bipartition satisfying (a), while G is a split graph of type B if its vertex set can be partitioned such that (b) or (c) holds. Note that the complement G of a split graph G is also a split graph. The class of split graphs is also known as the intersection of chordal and co-chordal graphs [START_REF] Földes | Split Graphs[END_REF].

Whenever G is a split graph, then χ r (G) = nα(G) + 1 (see [START_REF] Dereniowski | Rank coloring of graphs[END_REF]). Combining this fact with Theorem 1.1 we obtain Theorem 1.2 For any split graph G it holds that

χ r (G) = ω(G) + 1 if G is of type A, ω(G) if G is of type B.
In Section 2 we prove that the worst case ratio of the number of colors used by any on-line ranking algorithm and the number of colors used in an optimal off-line solution may be arbitrarily large. This negative result motivates us to strengthen an on-line algorithm by providing it with some additional information about the graph to be colored. This kind of approach is usually called semi on-line and has been widely studied, e.g., for various scheduling problems (see, e.g., [START_REF] Ebenlendr | Semi-Online Preemptive Scheduling: One Algorithm for All Variants[END_REF][START_REF] Kellerer | Semi on-line algorithms for the partition problem[END_REF][START_REF] Seiden | Semi-online scheduling with decreasing job sizes[END_REF]). In general a semi on-line algorithm may be given the values of some invariants of a graph in advance, i.e., before Presenter reveals the first vertex of a graph. The choice of the appropriate invariants is a separate and challenging problem, e.g., a semi on-line ranking algorithm for complete m-partite graphs K k1,...,km presented in [START_REF] Semanišin | A note on on-line ranking number of graphs[END_REF] knows in advance the values of k 1 , . . . , k m that uniquely describe the structure of the graph. In Section 3 we prove that for any ε > 0, there does not exist a semi on-line ranking algorithm that is (2ε)-competitive even if it is given the clique number of a split graph. The remaining parts of the paper focus on the statement and analysis of a 2-competitive semi on-line ranking algorithm that knows the clique number of a split graph in advance. In particular, in Section 4, prior to the formal description of the algorithm we introduce the concept of split tripartitions that are used for on-line classification of vertices. The idea is useful both for the formulation of the algorithm in Section 5 as well as for its analysis in Sections 6 and 7. The analysis is broken into two parts. First, in Section 6, we observe that though there are infinitely many possible Presenter's moves that may occur during the presentation of a split graph, it is possible to distinguish a finite number of types of moves. This fact is crucial, as it allows to represent all possible sequences of Presenter's moves as the directed walks of a well-structured digraph D, called the state transition digraph.

The state transition digraph is defined so that its walks reflect certain aspects of the evolution of graph structure during the game. It is important to point out that the directed walk corresponding to a particular game is independent of the ranking algorithm. Hence, a similar approach may also be used for the analysis of on-line algorithms for other combinatorial problems on split graphs.

From the results proved in this paper it follows that for split graphs there does not exist a constant competitive on-line ranking algorithm that could guarantee the usage of an interval of colors containing color 1.

Consequently, minimization of the largest color differs from the minimization of the number of colors which is our main interest. We remark on the former criterion in Section 8.

On-line Ranking

The main purpose of this section is to describe Presenter's strategy from which it follows that there does not exist a constant competitive on-line ranking algorithm for split graphs. This serves as the main reason to consider semi on-line algorithms.

Theorem 2.1 For any on-line ranking algorithm A and any integer p > 0, there exists a split graph G such that χ A (G)/χ r (G) ≥ p.

Proof: Let A be an arbitrary on-line ranking algorithm. If A assigns color 1 to v 1 , then Presenter fixes v 1 to be the center of a star S n (which is a split graph) and continues the presentation of the remaining vertices, thus forcing A to color them with pairwise different colors. This yields

χ A (S n ) = n, while χ r (S n ) = 2.
Therefore, let us assume without loss of generality that A used color k > 1 for the first vertex. Also note that since we describe a strategy of Presenter, there is no loss of generality in assuming that

v 1 v 2 ∈ E(G).
Presenter maintains a bipartition (C, I) of the vertex set, i.e., as soon as the revealed vertex gets colored, Presenter assigns it either to the independent set I or to the set C inducing a clique. The only exception is the decision on the assignment of the first vertex which is postponed until the second vertex is colored. Then, a vertex with the smaller color is assigned to C, while the other one is assigned to I. From now on, for i > 2, each vertex v i revealed by Presenter is joined to all vertices currently in C. If A uses for v i a color smaller than k, then v i is assigned to C. Otherwise, it is assigned to I. The strategy of assigning vertices with the smallest colors to C ensures that any A is forced to introduce a new color whenever a subsequent vertex is revealed (notice that C induces a clique, while reusing a color of any vertex from I spoils ranking). Consequently, χ A (G) = n. On the other hand, since A started with color k, the number of vertices assigned to C is at most k. This also bounds the clique number of a graph used by Presenter, i.e., ω(G) ≤ k + 1, and since Presenter constructs a split graph of type B, we have χ r (G) ≤ k + 1. Hence, the difference χ A (G)χ r (G) as well as χ A (G)/χ r (G) may be arbitrarily large. ✷

Lower Bounds for Semi On-line Ranking

In this section we argue that the knowledge of an upper bound on the clique number of a graph is a prerequisite for any semi on-line ranking algorithm to be constant competitive in the class of split graphs. Moreover, in the first theorem we reveal that even when the clique number of a split graph is given in advance, the algorithm has to satisfy some additional conditions; for if not, it is not constant competitive.

Theorem 3.1 Let A be a semi on-line ranking algorithm that is given ω and let k be one of the colors that

A used for the first two vertices. If k < ω + 1, then for any p > 0, there exists a split graph Proof: We use the strategy of Presenter from Theorem 2.1 and prove that its slight modification is also successful against any A that is given ω but colors v 1 or v 2 with color k < ω + 1. The case of k = 1 is trivial. Without loss of generality we may assume that v 1 was assigned color k = ω and v 2 some color greater than k. According to the strategy, v 1 gets assigned to C, while v 2 is assigned to I. The game continues and since the number of colors smaller than k is limited, either A loses because it may be forced to use in I arbitrarily many colors greater than k (they all have to be pairwise different because of ranking) or it is faced with the set C that consists of the vertices colored 2, . . . , k. As long as |C| < ω, the algorithm is not allowed to use color 1 for v i , since it would be immediately assigned to C and used by Presenter to force an arbitrary number of new colors by presenting a star with the central vertex v i . On the other hand, there are no more permissible colors smaller than k and hence using new colors greater than k for v i and for arbitrarily many subsequent vertices is unavoidable. ✷

G such that ω(G) ≤ ω and χ A (G)/χ r (G) ≥ p. v 1 (12) v 2 (17) v 3 (6) v 4 (10) (a) v 1 (12) v 2 (17) v 4 (10) v 5 (7) v 3 (6) v 6 (4) (b) v 1 (12) v 2 (17) v 3 (6) v 4 (10) v 5 (7) v 6 (4) v 7 (13) (c)
It is worth pointing out that Presenter's strategies used in the preceding theorems do not work if for both vertices v 1 , v 2 the algorithm uses colors greater than the clique number. Since Presenter adds to C one of these vertices, at most ω -1 colors smaller than ω + 1 may further be required to color all vertices in C. Therefore, the algorithm can save color 1 until ω colors are already present in C and it can safely use it for any subsequent vertex which will undoubtedly belong to I. In the next theorem we prove that for any ε > 0, there does not exist a semi on-line algorithm A that is (2ε)-competitive, even when A is given the clique number of a split graph G and colors v 1 , v 2 using colors greater than ω(G).

Theorem 3.2

Let A be a semi on-line ranking algorithm that is given the clique number of a graph. Then, there exists a split graph G such that χ A (G) ≥ 2χ r (G) -1.

Proof: Let k be the color used by A for the first vertex. By Theorem 3.1, k ≥ ω + 1. As in the previous proofs, Presenter maintains a bipartition (C, I) of the vertex set. The presentation starts with two adjacent vertices. Then, each vertex v i , i > 2, revealed by Presenter is adjacent to all vertices currently in C and for even values of i it is also adjacent to v i-1 (see Figure 1(a) -(b)). After the presentation of a vertex v i , when i is even, the colors of v i and v i-1 are compared and the vertex with the lower color is added to C while the one with the higher color is added to I. It follows directly from the construction that no color, which has already been assigned to a vertex in C, can be reused for the currently presented vertex v i . To see that the same holds for colors used in I, observe that for any vertex v ∈ I, there exists u ∈ C that is adjacent to v and v i , and such that c(u) < c(v). Hence, because of ranking, we get χ A (G i ) = i.

On the other hand, for every second round the clique number increases, i.e., ω(G i ) = i/2 + 1 when i is even, and ω(G i ) = (i + 1)/2 otherwise. Since G i is a split graph of type B, χ r (G i ) = ω(G i ) and after an odd round we have

χ A (G i ) = 2χ r (G i ) -1 (see Figure 1(c)). ✷
A natural question of the existence of a 2-competitive semi on-line ranking algorithm will be answered in the affirmative in Section 5. However, before we can formulate our algorithm, we need to provide some structural properties of split graphs. These properties are essential for the statement and analysis of the algorithm.

Split Tripartitions

As we will see in the next section, an important feature of our semi on-line ranking algorithm is its ability to maintain a specific classification of the vertices revealed by Presenter. In order to formally describe the classification process we have to define the split tripartition, which in turn relies on the notion of a simplicial vertex, i.e., a vertex whose closed neighborhood induces a clique. Since the class of split graphs is equal to the intersection of chordal and co-chordal graphs each vertex of a split graph G is simplicial in G or its complement G. The set of vertices that are simplicial as well in G as in G is of special importance for the above-mentioned classification.

Definition 4.1

The split tripartition of V (G) is its partition (C, S, I) such that each vertex in C is not simplicial in G, and each vertex in I is not simplicial in G, while S consists of all vertices that are simplicial both in G and in G.

Clearly, the vertex set of every split graph has a unique split tripartition. From the above definition there follow simple but important properties of split tripartitions. We state them here for a further reference. In the remaining part of this section we analyze selected relations between vertices of two split graphs G and H such that G is obtained from H by adding a vertex v (possibly with some incident edges). The properties will be further used in the analysis of a single round of the on-line ranking game in Section 5 as well as for the definition of types of Presenter's moves introduced in Section 6. In the following two lemmas we distinguish important configurations in the neighborhood of the abovementioned vertex v. In order to close the algorithmic gap we define a semi on-line algorithm Split Ranking (SR for short), which for any split graph G, given its clique number ω, uses at most 2χ r (G) colors. Algorithm SR processes every vertex in three stages: presentation, classification and coloring. We start with an informal description of these three stages of SR.

The main purpose of the presentation stage is to update the structure of the graph. The new vertex v i and the edges E i = {v i v j ∈ E(G) | j < i} revealed by Presenter are added to the graph G i-1 , which results in the graph G i . Revealing a subsequent vertex together with some edges provides a new piece of structural information on the target graph G.

Then, the classification stage begins. Its purpose is the computation of the split tripartition

(C i , S i , I i ) of V (G i ).
The set S i can be seen as a buffer that holds vertices that cannot be placed in C i or I i . A vertex v is kept in the buffer until it becomes clear that in some round v can be moved to one of the two other sets of the split tripartition, i.e., when v is no longer simplicial either in G or G. Recall that, by Property 4.2, in contrast to the assignment of vertices to S i , any assignment to C i or I i is permanent in the sense that C i ⊆ C j and I i ⊆ I j for each j > i. Though not important for the formulation of our algorithm, this fact is crucial for its analysis.

The coloring stage relies on two variables lc and hc with the names being abbreviations for lower and higher color, respectively. Their initial values are equal to 2ω + 2 and are assigned in the initialization stage of SR, that is, prior to the presentation of v 1 . In the coloring stage, SR uses color 1 for every vertex v i assigned to I i . Otherwise, the color for v i is selected greedily with respect to the interval [lc, hc]. More precisely, SR uses color lc, provided that this results in a ranking of G i . If this is not possible, SR checks color lc -1 and whenever the color is permissible, lc decreases by 1 and its new value is used as the color for v i . Otherwise, i.e., if both colors lc and lc -1 violate the definition of ranking, then v i is colored with the color obtained after incrementation of hc by 1. At the end of the coloring stage it holds that {c(v 1 ), . . . , c(v i )} = {1} ∪ {lc, . . . , hc} or {c(v 1 ), . . . , c(v i )} = {lc, . . . , hc}. See Algorithm 1 for the pseudocode of the algorithm SR.

Algorithm 1 Split ranking SR (ω); Begin V (G 0 ) ← ∅, E(G 0 ) ← ∅, C ← ∅, S ← ∅, I ← ∅; // initialization i ← 0; lc ← 2ω + 2; hc ← lc; repeat i ← i + 1; // presentation read (v i , E i ); V (G i ) ← V (G i-1 ) ∪ {v i }; E(G i ) ← E(G i-1 ) ∪ E i ; compute the split tripartition (C i , S i , I i ) of V (G i ); // classification if v i ∈ I i then // coloring c(v i ) ← 1; else if lc is permissible for v i then c(v i ) ← lc; else if lc -1 is permissible for v i then lc ← lc -1; c(v i ) ← lc; else hc ← hc + 1; c(v i ) ← hc;
until end of input; End. Now, let us consider an example of the execution of SR presented in Figure 2. Since the first round always results in the assignment of v 1 to S 1 , we depict the remaining rounds R 2 , . . . , R 8 . The description of a particular round R i , i ∈ {2, . . . , 8}, includes the structure of G i and the split tripartition

(C i-1 , S i-1 , I i-1 ) of V (G i-1
). We use arrows to depict the classification of the appropriate vertices in S i-1 and the assignment of v i to C i , S i or I i . Since SR receives the clique number in advance (in this case ω = 4), the initialization of the variables results in hc = lc = 10. For each round, the values of lc and hc at the end of the round are also given. Note that lc decreases in rounds R 2 , R 4 and R 7 . The only round in which SR uses color 1 is R 5 (v 5 is classified to I 5 ). The value of hc increases in R 8 . Since v 8 is adjacent to v 4 and v 6 (both with color 8) v 8 must receive a color greater than 8, for otherwise we would not have a ranking. Consequently, neither lc nor lc -1 is permissible for v 8 . Therefore, SR increases the value of hc and assigns it to v 8 .

Presenter's Moves

In order to analyze the performance of our algorithm we introduce the notion of the state transition digraph, which formally represents all possible states of the on-line ranking game. The vertices of the state transition digraph are called states while arcs are called transitions. For any transition (s, s ′ ), the states v 2 (9)

I 1 C 1 S 1 v 1 (10) C 2 S 2 I 2 v 3 (9) v 1 (10) v 2 (9) v 3 (9) v 2 (9) v 4 (8) v 3 (9) v 1 (10) v 4 (8) v 5 (1) v 2 (9) v 1 (10) v 5 (1) v 6 (8) v 2 (9) v 5 (1) v 2 (9) v 7 (7) v 5 (1) v 2 (9)
v 1 (10) s and s ′ are called pre-state and post-state, respectively. In what follows each move of Presenter will be thought of as an event that causes a transition from the current state to the appropriate post-state.

C 3 S 3 I 3 C 4 S 4 I 4 C 5 S 5 I 5 C 6 S 6 I 6 C 7 S 7 I 7 v 4 (8) v 4 (8) v 6 (8) v 3 (9) v 1 (10) v 1 (10) v 6 (8) v 8 (11) v 3 (9) v 3 (9) v 4 (8) v 7 (7) (R 2 ) (R 3 ) (R 4 ) (R 5 ) (R 8 ) (R 7 ) (R 6 )
More formally, let G be a family of graphs that are complete or edgeless, and let D = (W, T ) be an infinite digraph with the vertex set W and arc set T . Moreover, let ϕ : G → W (D) be a bijection. We say that the digraph D is the state transition digraph if for any H, H ′ ∈ G we have (ϕ(H), ϕ(H ′ )) ∈ T (D) if and only if there exist a split graph G i-1 such that G i-1 [S i-1 ] ≃ H and Presenter's move

P i = (v i , E i ) resulting in G i for which G i [S i ] ≃ H ′ .
Observe that, for a particular game, the sequence of graphs (G 0 , G 1 , . . . , G i ), G 0 ≃ N 0 , resulting from Presenter's moves (P 1 , P 2 , . . . , P i ) corresponds to the directed walk

(ϕ(G 0 [S 0 ]), ϕ(G 1 [S 1 ]), . . . , ϕ(G i [S i ]
)) in D. Also note that, by the definition, for any transition (s, s ′ ) there may exist non-isomorphic split graphs

G k-1 , G l-1 such that G k-1 [S k-1 ] ≃ G l-1 [S l-1 ] ≃ ϕ -1 (s) and G k [S k ] ≃ G l [S l ] ≃ ϕ -1 (s ′ ).
In what follows we slightly simplify our notation by writing

G[S i ] instead of G i [S i ] and N (v i ) in place of N Gi (v i ).
Since ϕ is a bijection, there will be also no ambiguity whenever we use H instead of ϕ(H), as a label for a vertex of D, e.g., K 2 instead of ϕ(K 2 ), or when we write "state G[S i ]" in place of "state ϕ(G[S i ])".

Though the number of states is infinite, we distinguish a finite number of types of Presenter's moves. This considerably simplifies the analysis of the coloring stage. The type of a move P i = (v i , E i ) depends solely on the pre-state G[S i-1 ] and the adjacency of v i to the vertices in the sets C i-1 , S i-1 and I i-1 of the split tripartition (C i-1 , S i-1 , I i-1 ) of V (G i-1 ). Similarly, the post-state resulting from P i is uniquely determined by the pre-state and the adjacency conditions, and it can be easily calculated. Therefore, the ...

v i (S 2 ) C i-1 S i-1 I i-1 ... ... v i C i-1 S i-1 I i-1 (S 3 )
...

v i (S 4 ) C i-1 S i-1 I i-1 ... ... v i (S 1 ) C i-1 S i-1 I i-
I i-1 ⊆ I i ).
To make the figures and further analysis more clear, we omit all parts of G i-1 that are irrelevant for the classification and we select symbols for the types of moves so that they reflect the classification of v i , i.e., the symbols S, C and I are used when v i is classified to S i , C i or I i , respectively. The list of the types of moves was organized in such a way that it allows for a clear proof of its completeness in Lemma 6.1 and so that it reflects all possible migrations of vertices from S i-1 to C i or I i . In the next section we classify rounds of the on-line ranking game as won, tie or lost by SR. As we will see later, the result of each round strongly depends on the type of Presenter's move. Some types that seem to be almost the same may differ significantly. For instance, when Presenter makes a move of type I 5 , the vertex v i is adjacent to all vertices in S i-1 , while in a move of type I 4 the set S i-1 contains a vertex that is not adjacent to v i (see Figure 5). In the next section we argue that this seemingly insignificant difference causes that SR always wins if Presenter makes a move of type I 5 , and it looses or eventually ties in the latter case. Also, the results of the rounds with moves of "similar" types I 1 and S 1 may differ, e.g., because of reusing a color from previous rounds, when moves of type S 1 form some specific sequences (we address this issue in Lemma 7.2). There are also some types of moves, e.g., I 3 , I 6 and C 1 , C 5 that we distinguish mainly for the completeness and clearness of the argument.

Types of Presenter's moves:

S 1 Pre-state: G[S i-1 ] ≃ N p , p ≥ 0 (S • 1 when p = 0, S • 1 when p > 0). Adjacency conditions: N (v i ) ∩ I i-1 = ∅ and C i-1 ⊆ N (v i ) and N (v i ) ∩ S i-1 = ∅. Post-state: G[S i ] ≃ N p+1 . S 2 Pre-state: G[S i-1 ] ≃ K p , p ≥ 2.
Adjacency conditions:

N (v i ) ∩ I i-1 = ∅ and C i-1 ⊆ N (v i ) and S i-1 ⊆ N (v i ). Post-state: G[S i ] ≃ K p+1 . ... Kr v i C i-1 S i-1 I i-1 (C 5 ) ... ... ... Kr v i C i-1 S i-1 I i-1 (C 1 ) Kr ... v i (C 2 ) C i-1 S i-1 I i-1 ... Kr v i C i-1 S i-1 I i-1 (C 3 )
...

Kr

...

v i I i-1 S i-1 C i-1 (C 4 )
... ...

S 3 Pre-state: G[S i-1 ] ≃ N p , p ≥ 1.
Adjacency conditions:

N (v i ) ∩ I i-1 = ∅ and C i-1 ⊆ N (v i ) and |N (v i ) ∩ S i-1 | = 1. Post-state: G[S i ] ≃ K 2 . S 4 Pre-state: G[S i-1 ] ≃ K p , p ≥ 2.
Adjacency conditions:

N (v i ) ∩ I i-1 = ∅ and C i-1 ⊆ N (v i ) and |N (v i ) ∩ S i-1 | = p -1. Post-state: G[S i ] ≃ N 2 . C 1 Pre-state: G[S i-1 ] ≃ N p , p ≥ 1.
Adjacency conditions:

N (v i ) ∩ I i-1 = ∅ and C i-1 ⊆ N (v i ) and t = |N (v i ) ∩ S i-1 | ≥ 1. Post-state: G[S i ] ≃ N t . C 2 Pre-state: G[S i-1 ] ≃ K p , p ≥ 2.
Adjacency conditions:

N (v i ) ∩ I i-1 = ∅ and C i-1 ⊆ N (v i ) and |N (v i ) ∩ S i-1 | = p -1. Post-state: G[S i ] ≃ N 0 . C 3 Pre-state: G[S i-1 ] ≃ N p , p ≥ 0 (C • 3 when p = 0, C • 3 when p > 0). Adjacency conditions: N (v i ) ∩ I i-1 = ∅ and C i-1 ⊆ N (v i ) and N (v i ) ∩ S i-1 = ∅. Post-state: G[S i ] ≃ N 0 . C 4 Pre-state: G[S i-1 ] ≃ K p , p ≥ 2.
Adjacency conditions:

N (v i ) ∩ I i-1 = ∅ and C i-1 ⊆ N (v i ) and S i-1 ⊆ N (v i ). Post-state = pre-state. C 5 Pre-state: G[S i-1 ] ≃ N p , p ≥ 2.
Adjacency conditions:

N (v i ) ∩ I i-1 = ∅ and C i-1 ⊆ N (v i ) and t = |N (v i ) ∩ S i-1 | ≥ 2. Post-state: G[S i ] ≃ N t . ... ... Kr ... v i (I 1 ) S i-1 I i-1 C i-1 ... ... ... Kr v i (I 2 ) S i-1 I i-1 C i-1 ... ... Kr v i (I 3 ) S i-1 I i-1 C i-1 ... ... Kr v i (I 4 ) S i-1 I i-1 C i-1 Kr ... v i (I 7 ) S i-1 I i-1 C i-1 Kr ... v i (I 6 ) S i-1 I i-1 C i-1 ... ... Kr v i S i-1 I i-1 (I 5 ) C i-1
Fig. 5: The types of moves for which vi is classified to Ii

I 1 Pre-state: G[S i-1 ] ≃ N p , p ≥ 0. Adjacency conditions: N (v i ) ∩ I i-1 = ∅ and C i-1 N (v i ) and N (v i ) ∩ S i-1 = ∅.
Post-state = pre-state.

I 2 Pre-state: G[S i-1 ] ≃ N p , p ≥ 1.
Adjacency conditions:

N (v i ) ∩ I i-1 = ∅ and C i-1 N (v i ) and |N (v i ) ∩ S i-1 | = 1. Post-state: G[S i ] ≃ N 0 . I 3 Pre-state: G[S i-1 ] ≃ K p , p ≥ 2.
Adjacency conditions:

N (v i ) ∩ I i-1 = ∅ and C i-1 N (v i ) and N (v i ) ∩ S i-1 = ∅. Post-state = pre-state. I 4 Pre-state: G[S i-1 ] ≃ K p , p ≥ 2.
Adjacency conditions:

N (v i ) ∩ I i-1 = ∅ and C i-1 N (v i ) and 1 ≤ t = |N (v i ) ∩ S i-1 | ≤ p -1. Post-state: G[S i ] ≃ K p-t . I 5 Pre-state: G[S i-1 ] ≃ K p , p ≥ 2.
Adjacency conditions:

N (v i ) ∩ I i-1 = ∅ and C i-1 N (v i ) and S i-1 ⊆ N (v i ). Post-state: G[S i ] ≃ N 0 . I 6 Pre-state: G[S i-1 ] ≃ K p , p ≥ 2.
Adjacency conditions:

N (v i ) ∩ I i-1 = ∅ and C i-1 ⊆ N (v i ) and N (v i ) ∩ S i-1 = ∅.
Post-state = pre-state.

I 7 Pre-state: G[S i-1 ] ≃ K p , p ≥ 3.
Adjacency conditions:

N (v i ) ∩ I i-1 = ∅ and C i-1 ⊆ N (v i ) and 1 ≤ t = |N (v i ) ∩ S i-1 | ≤ p -2. Post-state: G[S i ] ≃ K p-t . post-state N 0 N 1 ≃ K 1 N 2 N 3 • • • K 2 K 3 K 4 • • • pre-state N 0 I 1 , C • 3 S • 1 - - - - - N 1 ≃ K 1 I 2 , C • 3 I 1 , C 4 S • 1 - S 3 - - N 2 I 2 , C • 3 C 1 I 1 , C 1 , C 5 S • 1 S 3 - - N 3 I 2 , C • 3 C 1 C 1 , C 5 I 1 , C 1 , C 5 S 3 - - • • • • • • K 2 I 5 , C 2 I 4 S 4 - I 3 , I 6 , C 4 S 2 - K 3 I 5 , C 2 I 4 S 4 - I 4 , I 7 I 3 , I 6 , C 4 S 2 K 4 I 5 , C 2 I 4 S 4 - I 4 , I 7 I 4 , I 7 I 3 , I 6 , C 4 • • • • • • • • •
Tab. 1: Selected states and the appropriate types of Presenter's moves and of type I 5 , when

|S i-1 ∩ N (v i )| = |S i-1 | = p.
If none of these conditions is satisfied, then the move is of type I 4 .

Case 5. [N (v i ) ∩ I i-1 = ∅ and C i-1 ⊆ N (v i ) and G[S i-1 ] ≃ N p , p ≥ 0]
Note that the only types of moves that can be taken into account are C 1 , C • 3 and C • 3 . If p = 0, then we have a move of type C • 3 . For p > 0, the move is of type

C • 3 , when N (v i ) ∩ S i-1 = ∅, and of type C 1 , when |S i-1 ∩ N (v i )| ≥ 1. Case 6. [N (v i ) ∩ I i-1 = ∅ and C i-1 ⊆ N (v i ) and G[S i-1 ] ≃ K p , p ≥ 2] It is enough to consider C 2 and C 4 . By Lemma 4.2(b) we have that |S i-1 ∩ N (v i )| ≥ p -1. Hence, for any p ≥ 2, we have a move of type C 2 , when |S i-1 ∩ N (v i )| = p -1, while for |S i-1 ∩ N (v i )| = p the move is of type C 4 .
✷ Though there are infinitely many possible states, the number of types of moves is finite. A closer analysis of the state transition digraph's structure reveals some interesting properties that are crucial when proving 2-competitiveness of SR. See Table 1 for a collection of representative states and types of moves that correspond to the appropriate transitions.

Analysis of the Coloring Stage

Let π = (v 1 , . . . , v n ) be a fixed ordering of the vertices of a split graph G and let r i = χ SR (G i , π)/χ r (G i ) for each i ∈ {1, . . . , n}. In order to prove the main result we have to analyze all possible sequences (r n ).

Obviously r i ≥ 1 and χ SR (G i , π)χ SR (G i-1 , π) ∈ {0, 1} for each ordering π and for each i > 1.

Concerning the denominator of r i observe that it may differ from that of r i-1 when the move P i results in the increase of the clique number but also when it changes the type of a split graph. A Presenter's move that changes the type from A to B (B to A) is called an AB-move (BA-move, respectively). If the type is not changed the move is called an X-move. Since a BA-move P i cannot increase the clique number, we have ω(G i ) = ω(G i-1 ) and consequently

χ r (G i ) A = ω(G i ) + 1 = ω(G i-1 ) + 1 B = χ r (G i-1 ) + 1. (1)
Analogously, since every AB-move increases the clique number, i.e., ω(G i ) = ω(G i-1 ) + 1, we have

χ r (G i ) B = ω(G i ) = ω(G i-1 ) + 1 A = χ r (G i-1 ). (2)
For X-moves the types of G i and G i-1 are the same. Therefore, an increase of the clique number implies an increase of the ranking number. It finally follows that χ r (G i )χ r (G i-1 ) ∈ {0, 1} for each i > 1.

The above-mentioned properties let us classify the rounds of our game. We use names which represent the viewpoint of the algorithm. A round R i is said to be:

(a) a tie round, if χ r (G i ) = χ r (G i-1 ) and χ SR (G i , π) = χ SR (G i-1 , π), (b) a lost round, if χ r (G i ) = χ r (G i-1 ) and χ SR (G i , π) = χ SR (G i-1 , π) + 1, (c) a won round, if χ r (G i ) = χ r (G i-1 ) + 1 and χ SR (G i , π) ≤ χ SR (G i-1 , π) + 1.
Consequently, for a tie round r i = r i-1 , while for a lost one r i > r i-1 . Note that without loss of generality we may assume that whenever i is large enough, χ SR (G i , π) > χ r (G i ), i.e., r i > 1 (for otherwise SR would be optimal). Thus, for a won round we have that r i < r i-1 , except for the several rounds at the very beginning of the game when r i = 1.

The type of a round R i = (P i , A i ) depends both on Presenter's move P i and the algorithm's response A i .

Let us analyze their interactions in a more detailed manner, in particular, we focus on distinguishing won, lost and tie rounds.

Observe that a graph G is of type A if and only if S of the tripartition (C, S, I) of V (G) is empty, which follows from the uniqueness of the split bipartition of V (G) for graphs of this type. Thus, the necessary condition for the move P i to be a BA-move is its post-state to be N 0 . The possible types of such moves are: I 1 , I 2 , I 5 , C 2 and C 3 . Note that a move of type I 1 does not change the type of a split graph, while no move of type C • 3 may occur when G i-1 is of type B. Following these observations, we conclude that the only BA-moves are those of type C 2 , C • 3 , I 2 and I 5 . By Equation ( 1) and by the definition of a won round, whenever Presenter makes one of these moves, the round is won.

Let us now analyze the AB-moves. Since, as noted before, a split graph is of type A if and only if the set S of the split tripartition of its vertex set is empty, the pre-state of each AB-move is N 0 . Hence, the only candidates for AB-moves are the moves of type S • 1 , I 1 and C • 3 . However, if G i-1 is of type A, then each move of type I 1 or C • 3 results in G i also of type A. This implies that the only AB-move is a move of type S • 1 . In order to avoid tedious analysis of the algorithm's responses we assume that whenever Presenter makes a move of type S • 1 , the algorithm uses a new color, and since by Equation (2), χ r (G i ) = χ r (G i-1 ) the round is lost. The only exception is R 1 = (P 1 , A 1 ) with P 1 of type S • 1 which is a won round. The remaining moves are X-moves. Recall that since X-moves do not change the type of a split graph, the ranking number increases only if the clique number does, i.e., when ω(G i ) > ω(G i-1 ). It is not hard to see that the only X-moves that increase the clique number are the moves of type S 2 , S 3 , C 1 , C • 3 , C 4 and C 5 . Hence, the corresponding rounds are won. If Presenter makes a move of type I 1 , I 3 , I 4 , I 6 or I 7 , then SR obviously reuses color 1 and since none of these moves increases the clique number, we have tie rounds, with the only exception, when the algorithm uses color 1 for the first time. The round is lost then, but only once per game. To simplify the analysis, all rounds in which Presenter makes a move of type S 4 are assumed to be lost, while for any move of type S • 1 the round may be lost or tie (see the detailed analysis in the proof of Lemma 7.2).

Before we continue the analysis let us summarize the above observations in the form of the following lemma.

Conclusions

The semi on-line algorithm SR presented in this paper uses at most 2χ r (G) colors for any split graph G. Recall that the optimization goal used in this work, i.e., minimization of the number of pairwise different colors assigned by the algorithm, is different from the maximum color criterion. We now point out that SR is constant competitive for the latter criterion as well. By construction, SR assigns color 1 to a vertex v i that belongs to I i , and one can prove that if v i ∈ S i , then c(v i ) equals the value of lc at the end of round R i . Moreover, if a move corresponding to some round R i is of one of the types C 1 , . . . , C 5 , then |C i | > |C i-1 |. Therefore, since |C n | ≤ ω(G) there are at most ω(G) rounds with the moves of types C 1 , . . . , C 5 , which implies that hc increases at most ω(G) times. Consequently, the maximum color used by SR is 3ω(G) + 2, which means that SR is 3-competitive in the sense of the second optimization criterion.

Although for minimization of the number of colors we have proved that SR is 2-competitive provided that ω(G) is given, it is worth pointing out that it suffices when SR only knows an upper bound on ω(G). In fact, we have proved that the algorithm works correctly when lc and hc are set to at least 2ω(G) + 2 in the initialization stage. Therefore, every algorithm that can find an upper bound k on ω(G) and calls SR(k) is also 2-competitive. In particular, there exists a 2-competitive algorithm that is given in advance the order n of a graph G.

Observe that a similar reasoning cannot be applied to semi on-line algorithms that know n, whenever we minimize the maximum color. We can argue, however, that there exists a (3 √ n + 2)-competitive algorithm B of such type. To this end we first extend SR (let SR ′ denote the corresponding new algorithm) in such a way that whenever lc reaches the value of 1 in round i, then in the subsequent rounds SR ′ uses pairwise different colors that are greater than or equal to the value of hc in round i. Let B proceed by calling SR ′ ( √ n). If ω(G) < √ n, then as argued in the proof of Lemma 7.2, the value of lc is greater than 1 during the entire execution of SR. Therefore, the largest color used by B is bounded by 3 √ n + 2 and the claim trivially follows. Otherwise, χ r (G) ≥ √ n and SR ′ produces a vertex ranking such that for any graph G, the maximum color never exceeds n. Consequently, SR ′ is √ n-competitive in this case. On the other hand, 3 √ n + 2 constitutes an asymptotically tight bound, i.e., no semi on-line algorithm A, that is given n in advance, can be ( √ nε)-competitive for the maximum color minimization. Indeed, on the contrary, suppose that such an algorithm exists and consider two natural cases. If the first color used by A is less than √ n, then by an easy generalization of Theorem 3.1, there exists Presenter's strategy that forces A to use n colors for a graph G with χ r (G) ≤ √ n. On the other hand, if the first color used is at least √ n, then Presenter fixes G to be N n (note that χ r (N n ) = 1). Clearly, in both cases χ A (G)/χ r (G) ≥ √ n, which contradicts our assumption.

Since the lower bound given in Theorem 3.2 holds for both criteria (every vertex has a different color), an interesting direction for further research is a construction of a semi on-line ranking algorithm which is 2-competitive with respect to the minimization of the maximum color.

We finish with the remark that Dobrev et al. [START_REF] Dobrev | How much information about the future is needed?[END_REF] introduced a formal framework that allows to classify on-line problems according to how much information (advice bits) about the future input parts is needed for solving them optimally or with a specific competitive ratio (see also [START_REF] Bianchi | Online coloring of bipartite graphs with and without advice[END_REF][START_REF] Böckenhauer | On the advice complexity of online problems[END_REF] for other results). From the results proved in this paper it also follows that at least ⌊log 2 ω⌋ + 1 bits of advice are required for any on-line ranking algorithm to be constant competitive on split graphs and that this number of bits is sufficient to achieve a constant competitive ratio for both optimization criteria.

Theorem 1 . 1 (

 11 P. L. Hammer, B. Simeone,[START_REF] Hammer | The splittance of a graph[END_REF]) Let the vertex set of a split graph G be partitioned into an independent set I and a set C inducing a clique. Then, exactly one of the following conditions holds:

Fig. 1 :

 1 Fig. 1: An example for Theorem 3.2. Numbers in braces denote sample colors. Black vertices belong to C, white to I, while diamonds represent vertices before Presenter's decision on their assignment.

Property 4 . 1

 41 If G is a split graph and (C, S, I) is the split tripartition of V (G), then (a) G[S] is either a clique or an edgeless graph, (b) each vertex in S is adjacent to all vertices in C and has no neighbors in I.

Property 4 . 2

 42 Let G be a split graph and let H ≤ G such that V (G) \ V (H) = {v}. If (C, S, I) and (C ′ , S ′ , I ′ ) are the split tripartitions of V (H) and of V (G), respectively, then C ⊆ C ′ and I ⊆ I ′ .

Lemma 4 . 1 Lemma 4 . 2

 4142 There does not exist a split graph G that contains an induced subgraphH, V (G) \ V (H) = {v} such that for the split tripartition (C, S, I) of V (H) it holds that N G (v) ∩ I = ∅ and C N G (v).Proof: Suppose for a contradiction that there exists a split graph G with the given properties and let (C ′ , S ′ , I ′ ) be the split tripartition of V (G). Let x ∈ I and y ∈ C be selected in such a way that xv ∈ E(G) and yv / ∈ E(G). Observe that whenever xy ∈ E(G), then x is not simplicial in G and hencex ∈ C ′ . However, by Property 4.2, it holds that x ∈ I ′ , a contradiction. On the other hand if xy / ∈ E(G), then we get a contradiction by an analogous argument applied to G.✷ Let H be an induced subgraph of a split graph G such that V (G) \ V (H) = {v} and let (C, S, I) be the split tripartition of V (H).

( a )

 a If H[S] ≃ N p , for some p ≥ 0, and C N G (v), then |S ∩ N G (v)| ≤ 1. (b) If H[S] ≃ K p , for some p ≥ 2, and N G (v) ∩ I = ∅, then |S ∩ N G (v)| ≥ |S| -1. Proof: (a) Let (C ′ , S ′ , I ′ ) be the split tripartition of V (G). Assume, on the contrary, that |S ∩N G (v)| > 1 and let x, y ∈ S be the neighbors of v in G. Since x and y are not adjacent, the vertex v is not simplicial in G, i.e., v ∈ C ′ . Let u ∈ C \ N G (v). Since by Property 4.2 it holds that C ⊆ C ′ , the vertex u belongs to C ′ . Hence, C ′ contains both u and v that are not adjacent, a contradiction. Part (b) follows directly from (a), by examining the complement graph. ✷ 5 Semi On-line 2-competitive Algorithm

(lc = 9 ,Fig. 2 :

 92 Fig. 2: An example of the execution of the algorithm SR (rounds R2, . . . , R8). Numbers in braces denote the colors assigned by SR.

Fig. 4 :

 4 Fig. 4: The types of moves for which vi is classified to Ci

  [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF] The types of moves for which vi is classified to Si post-state is not required in move's type definition, but we explicitly give a description of each post-state to make the list of types more useful for further analysis. All types of moves are also presented in Figures3, 4 and 5. In each figure the structure of G i-1 is reflected by distinguishing its split tripartition while v i is shown separately, together with all edges in E i . The arrows, when present, show the result of the classification, i.e., they indicate whether v i or some vertices from S i-1 belong to C i , S i or I i (recall that by Property 4.2, C i-1 ⊆ C i and

	Kr	Kr	Kr	Kr
		Fig. 3:

Acknowledgements

We would like to acknowledge the anonymous referees for their valuable comments that permitted us to significantly improve the readability of the paper.

† This project has been partially supported by Narodowe Centrum Nauki under contract DEC-2011/02/A/ST6/00201 ‡ Partially supported by the Foundation for Polish Science (FNP) and by Narodowe Centrum Nauki under contract DEC-2011/02/A/ST6/00201 1365-8050 c 2013

In Figure 6 we use the types of moves to continue the analysis of the game presented in Figure 2. In particular, we depict a digraph whose arcs represent all transitions in the rounds R 1 , . . . , R 8 of the game. Each arc is labeled with the rounds in which the corresponding transitions occur and with the types of the appropriate Presenter's moves. Now, we argue that no case is missing and that the types of moves cover pairwise disjoint cases, i.e., for the given split tripartition of V (G i-1 ) every move satisfies the adjacency conditions of exactly one type. Lemma 6.1 For any split graph G i-1 , every Presenter's move P i = (v i , E i ) is of exactly one of the types I 1 , . . . , I 7 , S 1 , . . . , S 4 , C 1 , . . . , C 5 .

Proof:

In order to take into account all possible moves of Presenter we consider two complementary cases for each set of the split tripartition

Hence, the proof falls into eight natural cases, where by Lemma 4.1 two of them, for which N (v i ) ∩ I i-1 = ∅ and simultaneously C i-1 N (v i ) are not possible, so it is enough to consider the remaining six cases.

Observe that the only types of moves to consider are S • 1 , S • 1 , S 3 and C 5 . If p = 0, then we clearly have a move of type S • 1 . For p = 1, if S i-1 ∩ N (v i ) = ∅, then the move is of type S • 1 and of type S 3 , when

Similarly, for p ≥ 2, the move is of type S 3 or S • 1 , when v i has one neighbor or has no neighbors in S i-1 , respectively, while for

The only types of moves that can be taken into account are S 2 , S 4 , I 6 and I 7 . If S i-1 ∩ N (v i ) = ∅, then we clearly have a move of type

which directly corresponds to a move of type I 7 .

It will be enough to consider I 1 and I 2 . If p = 0, then obviously v i has no neighbor in S i-1 . Hence, the move is of type

The only types of moves to consider are I 3 , I 4 and

, when there exists v j , j < i, such that c(v j ) = 1, is tie, (c) I 1 , I 3 , I 4 , I 6 , I 7 , when there does not exist v j , j < i, such that c(v j ) = 1, is lost.

The above-mentioned properties of moves of various types allow us to prove the following result.

Lemma 7.2 Let R t , R q , t < q, be two lost rounds such that neither of them uses color 1 for the first time.

Then, there exists i, t < i < q, such that R i is won. Moreover, the first lost round is preceded by at least two won rounds.

Proof: Let D ′ be the subdigraph of the state transition digraph D, containing only these arcs of D that correspond to the rounds with the moves of types not mentioned in Lemma 7.1(a) (see Figure 7). It is crucial to observe that D ′ is acyclic (except for the loops). Consequently, any directed walk in D that represents transitions which occur during the game and contains no arc corresponding to a won round is a directed path in D ′ . Therefore, it remains to argue that there does not exist a directed path in D ′ containing two arcs that correspond to some lost rounds.

Looking for such directed paths, observe that whenever Presenter makes some number of moves of type S 1 in a row, i.e.,

or

the thesis follows if the color used by SR in response to the first move of the above sequences is further reused as a response to all the subsequent moves of type S • 1 , which results in rounds that are not lost. The same holds for sequences starting with S 4 , i.e.,

In fact any sequence (4) or ( 5) may be preceded by a sequence composed of the moves of types I 3 , I 4 , I 6 and I 7 . Similarly, there may be the rounds when Presenter makes a move of type I 1 between the moves in sequences (3)-( 5). However, all loops of D ′ correspond to the rounds that are tie or eventually one of them is lost, when color 1 is used for the first time. Therefore, we do not have to take them into account in this proof.

We continue with the assumption that the value of the variable lc is greater than 1 during the entire execution of the algorithm. We will justify this assumption later on. First we argue that for any execution of SR, the color used in round R i-1 , corresponding to the first move in any of the sequences (3)-( 5), can be reused in the subsequent rounds of these sequences. Observe that, as a result of round R i-1 , we have that v i-1 ∈ S i-1 and S i-1 is independent (see the post-states of S • 1 , S • 1 and S 4 ). Next, in round R i with a move of type S • 1 , the vertex v i is classified to S i and by the definition of S • 1 it holds that S i is also independent. Moreover, v i-1 ∈ S i . Since in the rounds with the moves of types S 1 , . . . , S 4 the algorithm uses neither color 1 nor color hc, it follows that c(v i-1 ) is the smallest color assigned to the vertices in

) does not violate the definition of ranking, and consequently, c(v i-1 ) is permissible also for v i .

It remains to prove that during every execution of the algorithm, the value of lc decreases at most 2ω times, which justifies our earlier assumption that lc is always greater than 1. Obviously, in every game round R 1 is won. It is also not hard to see that rounds R i , i > 1, are tie as long as G i is edgeless. Moreover, any round R i such that |E(G i )| ≥ 1 and E(G i-1 ) = ∅ is won. Thus, in every game the first lost round is always preceded by at least two won rounds. As argued earlier, each sequence (3)-( 5) is preceded by a won round, and contains at most one move corresponding to a lost round. By the definition of a won round, χ r (G i ) = χ r (G i-1 ) + 1. Hence, there are p ≤ χ r (G) ≤ ω(G) + 1 won rounds and at most p -1 ≤ ω(G) rounds that are lost. Consequently, there are at most 2ω(G) + 1 different values of lc used during the entire execution of SR and hence at most 2ω(G) moves may result in the decrease of lc. This implies that lc > 1 in each iteration of the main loop of SR. ✷ Theorem 7.1 For any split graph G we have χ SR (G) ≤ 2χ r (G).

Proof: Let π be any permutation of the vertices of G and let R i be the round in which the color of v i has been set, i ∈ {1, . . . , n}. We are going to prove by induction on i that for each i ∈ {1, . . . , n}

(ii) if there exists a round R j , j ≤ i, in which SR uses color 1, then r i ≤ 2.

First observe that G 1 has a single vertex, which means that χ SR (G 1 , π) = χ r (G 1 ) = 1 and the hypothesis holds. Assume now that (i) and (ii) hold for each i ′ ∈ {1, . . . , i} and we will prove the claim for G i+1 , i < n. The proof falls naturally into the three cases:

Case 1. R i+1 is a tie round. By the definition, χ r (G i+1 ) = χ r (G i ) and χ SR (G i+1 , π) = χ SR (G i , π). So, r i+1 = r i and the induction hypothesis completes the proof in this case.

Case 2. R i+1 is a won round.

We have that χ r (G i+1 ) = χ r (G i ) + 1 and χ SR (G i+1 , π) ≤ χ SR (G i , π) + 1. So, by (ii) (and analogously by (i))

and the hypothesis follows.

Case 3. R i+1 is a lost round.

Subcase 3.1 Let us first analyze the situation when R i+1 is the round in which color 1 was used for the first time. By assumption (i) we have

where the second equality follows directly from the definition of a lost round.

Subcase 3.2 Now assume that SR used for v i+1 some color larger than 1 and that color 1 has not been used in rounds R 1 , . . . , R i . Additionally, let i ′ = 0 if there was no lost round preceding R i+1 or let i ′ = max{j ∈ {1, . . . , i} | R j is lost} otherwise. Assume that there were k won rounds in {R i ′ +1 , . . . , R i }. By Lemma 7.2 we have that k ≥ 1 when i ′ > 0 and that k ≥ 2 when i ′ = 0. By the definition of a won round, χ r (G i ) = χ r (G i ′ ) + k. Notice that all rounds in {R i ′ +1 , . . . , R i } are either won or tie, which implies that χ SR (G i , π) ≤ χ SR (G i ′ , π) + k. Then,

We need to prove that r i+1 < 2. If i ′ = 0, then χ SR (G i ′ , π) = 0 and χ r (G i ′ ) = 0 and the thesis follows. Otherwise, by (i) of the induction hypothesis,

which proves (i).

Subcase 3.3 If for v i+1 the algorithm used a color larger than 1, but color 1 has already been used in one of the preceding rounds, then it is enough to notice that the first usage of color 1 always results in a lost round. The rest of the proof is analogous to Subcase 3.2 and we get r i+1 ≤ 2.

This completes the analysis of all possible cases, and since π was chosen arbitrarily, χ SR (G) ≤ 2χ r (G) follows. ✷