Semi-proper orientations of dense graphs

Júlio Araújo, Frédéric Havet, Claudia Linhares Sales, Nicolas Nisse, Karol Suchan

► To cite this version:

Júlio Araújo, Frédéric Havet, Claudia Linhares Sales, Nicolas Nisse, Karol Suchan. Semi-proper orientations of dense graphs. Discrete Applied Mathematics, 2025, 371, pp.196-217. 10.1016/j.dam.2025.04.020. hal-05380157

HAL Id: hal-05380157

https://inria.hal.science/hal-05380157v1

Submitted on 24 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Semi-proper orientations of dense graphs*

Julio Araujo¹, Frédéric Havet², Claudia Linhares Sales¹, Nicolas Nisse², and Karol Suchan³,⁴

¹ParGO, Universidade Federal do Ceará, Fortaleza, Brazil

²Université Côte d'Azur, CNRS, Inria, I3S, Sophia Antipolis, France

³Universidad Diego Portales, Santiago, Chile

⁴AGH University of Science and Technology, Krakow, Poland

November 24, 2025

**Abstract**

An *orientation* $D$ of a graph $G$ is a digraph obtained from $G$ by replacing each edge by exactly one of the two possible arcs with the same ends. An *orientation* $D$ of a graph $G$ is a *k-orientation* if the in-degree of each vertex in $D$ is at most $k$. An *orientation* $D$ of $G$ is *proper* if any two adjacent vertices have different in-degrees in $D$. The *proper orientation number* of a graph $G$, denoted by $\vec{\chi}(G)$, is the minimum $k$ such that $G$ has a proper $k$-orientation.

A *weighted orientation* of a graph $G$ is a pair $(D, w)$, where $D$ is an orientation of $G$ and $w$ is an arc-weighting $A(D) \to \mathbb{N} \setminus \{0\}$. A *semi-proper orientation* of $G$ is a weighted orientation $(D, w)$ of $G$ such that for every two adjacent vertices $u$ and $v$ in $G$, we have that $S_{(D,w)}(v) \neq S_{(D,w)}(u)$, where $S_{(D,w)}(v)$ is the sum of the weights of the arcs in $(D, w)$ with head $v$. For a positive integer $k$, a *semi-proper k-orientation* $(D, w)$ of a graph $G$ is a semi-proper orientation of $G$ such that $\max_{v \in V(G)} S_{(D,w)}(v) \le k$. The *semi-proper orientation number* of a graph $G$, denoted by $\vec{\chi}_s(G)$, is the least $k$ such that $G$ has a semi-proper $k$-orientation.

In this work, we first prove that $\vec{\chi}_s(G) \in \{\omega(G) - 1, \omega(G)\}$ for every split graph $G$, and that, given a split graph $G$, deciding whether $\vec{\chi}_s(G) = \omega(G) - 1$ is an NP-complete problem. We also show that, for every $k$, there exists a (chordal) graph $G$ and a split subgraph $H$ of $G$ such that $\vec{\chi}(G) \le k$ and $\vec{\chi}(H) = 2k-2$. In the sequel, we show that, for every $n \ge p(p+1)$, $\vec{\chi}_s(P_n^p) = \lceil \frac{3}{2}p \rceil$, where $P_n^p$ is the $p$th power of the path on $n$ vertices. We investigate further unit interval graphs with no big clique: we show that $\vec{\chi}(G) \le 3$ for any unit interval graph $G$ with $\omega(G) = 3$, and present a complete characterization of unit interval graphs with $\vec{\chi}(G) = \omega(G) = 3$. Then, we show that deciding whether $\vec{\chi}_s(G) = \omega(G)$ can be solved in polynomial time in the class of co-bipartite graphs. Finally, we prove that computing $\vec{\chi}_s(G)$ is FPT when parameterized by the minimum size of a vertex cover in $G$ or by the treewidth of $G$. We also prove that not only computing $\vec{\chi}_s(G)$, but also $\vec{\chi}(G)$, admits a polynomial kernel when parameterized by the neighbourhood diversity plus the value of the solution. These results imply kernels of size $4^{O(k^2)}$ and $O(2^k k^2)$, in chordal graphs and split graphs, respectively, for the problem of deciding whether $\vec{\chi}_s(G) \le k$ parameterized by $k$. We also present exponential kernels for computing both $\vec{\chi}(G)$ and $\vec{\chi}_s(G)$ parameterized by the value of the solution when $G$ is a cograph. On the other hand, we show that computing $\vec{\chi}_s(G)$ does not admit a polynomial kernel parameterized by the value of the solution when $G$ is a chordal graph, unless NP $\subseteq$ coNP/poly.

# 1 Introduction

All graphs in this work are simple and finite. For terms not defined here, we refer to [9, 12].

<footnote>*This work was supported by the STIC-AmSud project GALOP (Programa Regional STICAMSUD 19-STIC-05).</footnote>
A **(proper) k-colouring** of $G$ is a mapping $c: V(G) \to \{1, \dots, k\}$ such that $c(u) \neq c(v)$ for every edge $uv \in E(G)$. The **chromatic number** of $G$, denoted by $\chi(G)$, is the minimum $k$ such that $G$ admits a $k$-colouring. Determining the chromatic number of a given graph $G$ is one of the most studied problems in Graph Theory and it is one of the Karp's NP-hard problems [18].

An **orientation** $D$ of a graph $G$ is a digraph obtained from $G$ by replacing each edge by exactly one of the two possible arcs with the same ends. An orientation $D$ of a graph $G$ is a **$k$-orientation** if the in-degree of every vertex in $D$ is at most $k$. An orientation $D$ of $G$ is **proper** if any two adjacent vertices have different in-degrees in $D$. The **proper orientation number** of a graph $G$, denoted by $\vec{\chi}(G)$, is the minimum $k$ such that $G$ has a proper $k$-orientation. In other words, the values of the in-degrees in $D$ define a proper colouring of $G$ (with the first colour being zero). The existence of proper orientations was implicitly demonstrated by Borowiecki, Grytczuk and Pils\'niak in [10], who established that $\vec{\chi}(G) \le \Delta(G)$, where $\Delta(G)$ denotes the **maximum degree** of $G$. Thus,

$$ \chi(G) - 1 \le \vec{\chi}(G) \le \Delta(G). \qquad (1) $$

Afterwards, the proper orientation number was introduced in [1]. Since then, the proper orientation number has been studied by several authors and some parameters related to proper orientations were defined in the literature (for instance, see [1–7, 11, 13, 14, 19]).

In [5], it is shown that the proper orientation number of a tree is at most 4, and that there exist trees whose proper orientation number equals 4. A natural question is to ask how it can be generalized.

**Problem 1.1.** Which graph classes containing the trees have bounded proper orientation number?

Araujo et al. [6] proved that this is the case for cacti (their proper orientation number is bounded by 7), but left open the question for the class of outerplanar graphs. It was partly answered by Ai et al. [3], who proved that $\vec{\chi}(G) \le 3$ if $G$ is a triangle-free 2-connected outerplanar graph, and $\vec{\chi}(G) \le 4$ if $G$ is a triangle-free bridgeless outerplanar graph. This question was already asked for the more general subclasses of planar graphs, like outerplanar graphs or (all) planar graphs. In [5], the authors posed the following more general problem. Is $\vec{\chi}(G)$ upper bounded by a function of the treewidth or the maximum average degree of $G$? Recall that the **maximum average degree** of $G$, denoted by $\text{mad}(G)$, is the maximum value of $2|E(H)|/|V(H)|$ over all subgraphs $H$ of $G$. Note that $\text{mad}(G)$ and $\chi(G)$ are upper bounded by the treewidth of $G$ plus one, for every graph $G$, and that $\text{mad}(G)$ and $\chi(G)$ are bounded by constants in (outer)planar graphs. The above problem has very recently been solved by Chen, Mohar and Wu [11] who proved the following theorem, which can be seen as a generalization of a result of Dehghan and Havet [14] on the semi-proper orientation number (Theorem 1.5).

**Theorem 1.2** (Chen, Mohar and Wu [11]). For all graph $G$, we have

$$ \vec{\chi}(G) = \frac{\text{mad}(G)}{2} + \mathcal{O}\left(\frac{\chi(G) \log \chi(G)}{\log \log \chi(G)}\right). $$

Dehghan and Havet [14] introduced the notion of semi-proper orientations. A **weighted orientation** of a graph $G$ is a pair $(D, w)$, where $D$ is an orientation of $G$ and $w$ is an arc-weighting $A(D) \to \mathbb{N} \setminus \{0\}$. A **semi-proper orientation** of $G$ is a weighted orientation $(D, w)$ of $G$ such that, for every two vertices $u$ and $v$ adjacent in $G$, we have that $S_{(D,w)}(v) \neq S_{(D,w)}(u)$, where the **in-weight** of a vertex $v$, denoted $S_{(D,w)}(v)$, is the sum of the weights of the arcs in $(D, w)$ for which $v$ is the head, i.e.:

$$ S_{(D,w)}(v) = \sum_{z \in N_{D}^{\vec{v}}(v)} w(z, v), $$

where $N_{D}^{\vec{v}}(v) = \{z | (z, v) \in A(D)\}$ denotes the **in-neighbourhood** of $v$ in $D$. For a positive integer $k$, a **semi-proper $k$-orientation** $(D, w)$ of a graph $G$ is a semi-proper orientation of $G$ such that $\max_{v \in V(G)} S_{(D,w)}(v) \le k$. The **semi-proper orientation number** of a graph $G$, denoted by $\vec{\chi}_{s}(G)$, is the least $k$ such that $G$ has a semi-proper $k$-orientation. A semi-proper $k$-orientation $(D, w)$ is **optimum**
if $k = \vec{\chi}_s(G)$. In [14], it is shown that, for any graph $G$, there exists an optimum semi-proper orientation $(D, w)$ such that $w: A(D) \to \{1, 2\}$.

Note that every proper $k$-orientation $D$ of a graph $G$ gives a semi-proper $k$-orientation $(D, w)$ of $G$ such that $w(e) = 1$ for every $e \in A(D)$. Consequently, by (1), we have

$$ \chi(G) - 1 \le \vec{\chi}_s(G) \le \vec{\chi}(G) \le \Delta(G). \qquad (2) $$

The degeneracy $\delta^*(G)$ of a graph $G$ is defined as $\delta^*(G) = \max_{H \subseteq G} \delta(H)$, where $\delta(H)$ is the minimum degree of a vertex in $H$. Let $\omega(G)$ denote the maximum size of a clique in $G$. It is well known that:

$$ \omega(G) \le \chi(G) \le \delta^*(G) \le \Delta(G) + 1. \qquad (3) $$

A considerable difference between the parameters $\vec{\chi}$ and $\vec{\chi}_s$ is that the latter is monotone. Recall that a graph parameter $\gamma$ is **monotone** if $\gamma(H) \le \gamma(G)$ for every subgraph $H$ of $G$. As shown [6], the proper orientation number is not monotone, even when restricted to trees. In contrast, the semi-proper orientation number is.

**Lemma 1.3** (Dehghan and Havet [14]). If $H$ is a subgraph of $G$, then $\vec{\chi}_s(H) \le \vec{\chi}_s(G)$.

When dealing with induced subgraphs, we have the following more precise statement.

**Proposition 1.4.** Let $G$ be a graph and $v$ a vertex of $G$. Then, $\vec{\chi}_s(G - v) \le \vec{\chi}_s(G) \le \vec{\chi}_s(G - v) + 1$.

*Proof.* By Lemma 1.3, $\vec{\chi}_s(G - v) \le \vec{\chi}_s(G)$. Therefore it suffices to prove that $\vec{\chi}_s(G) \le \vec{\chi}_s(G - v) + 1$. Let $(D, w)$ be an optimum semi-proper orientation of $G - v$, i.e., with maximum in-weight $\vec{\chi}_s(G - v)$. Let $(D', w')$ be the semi-proper orientation of $G$ such that $D'$ agrees with $D$ on $G - v$ and $v$ has in-degree 0. Moreover, for every $u \in N(v)$, let $w'(v, u) = 1$ (so the in-weight of $u$ in $G$ equals the in-weight of $u$ in $G - v$ plus one). Finally, for every $u \in V(G) \setminus N[v]$ that has in-weight at least one in $(D, w)$, choose one in-going arc $(x, u)$ and let $w'(x, u) = w(x, u) + 1$. For every other arc $e$, $w'(e) = w(e)$. Then, $(D', w')$ is a semi-proper orientation of $G$ with maximum in-weight at most $\vec{\chi}_s(G - v) + 1$. $\square$

**Proposition 1.4** shows another major difference between $\vec{\chi}$ and $\vec{\chi}_s$, since there exist a graph $G$ and a vertex $v \in V(G)$ such that $\vec{\chi}(G - v) \le \vec{\chi}(G) - 2$. Indeed, Araujo et al. exhibit a **split graph** $G'$, a graph whose vertex-set can be partitioned into a clique and a stable set, such that $\vec{\chi}(G') = 2\omega(G') - 2$ and they show that, for any split graph $G$, $\vec{\chi}(G) \le 2\omega(G) - 2$. Therefore, for any vertex $v$ of the clique of $G'$, $\vec{\chi}(G' - v) \le 2\omega(G' - v) - 2 = 2\omega(G') - 4 = \vec{\chi}(G') - 2$ [4].

Thanks to Lemma 1.3, Dehghan and Havet [14] succeeded to prove lower and upper bounds for $\vec{\chi}_s(G)$ in function of $\mathrm{mad}(G)$, $\delta^*(G)$ and $\chi(G)$:

**Theorem 1.5** (Dehghan and Havet [14]). For any graph $G$, we have

$$ \left\lfloor \frac{\mathrm{mad}(G)}{2} \right\rfloor \le \vec{\chi}_s(G) \le \left\lfloor \frac{\mathrm{mad}(G)}{2} \right\rfloor + \chi(G) - 1 \quad \text{and} \quad \left\lfloor \frac{\delta^*(G) + 1}{2} \right\rfloor \le \vec{\chi}_s(G) \le 2\delta^*(G). $$

Recall that graphs with treewidth at most $k$ satisfy that $\delta^*(G) \le k$, and thus previous bounds apply to the class of bounded treewidth graphs. Tight constant upper bounds for the classes of trees, cacti, outerplanar and planar graphs for the semi-proper orientation number are presented in [14].

**Theorem 1.2** (and Theorem 1.5) states that the proper orientation number (and thus semi-proper orientation number) of sparse graphs is bounded. It also has corollaries for classes of dense graphs. If every graph $G$ of a class has maximum average degree bounded by a function of the clique number $\omega(G)$, then the proper and semi-proper orientation numbers are also bounded by a function of the $\omega(G)$. Split graphs, interval graphs and cobicartite graphs form such graph classes. For each of these classes, a natural question is then to find the minimum function $f$ (resp. $g$) such that $\vec{\chi}(G) \le f(\omega(G))$ (resp. $\vec{\chi}_s(G) \le g(\omega(G))$) for every graph $G$ in the class.
Regarding the computational complexity, deciding if the proper orientation number $\vec{\chi}(G)$ of a graph $G$ is at most 2 is an NP-complete problem even if $G$ is planar and bipartite. Moreover, deciding whether $\vec{\chi}(G) \le k$ is NP-complete for a graph $G$ and a positive integer $k$ given as inputs [4]. In [7], Araujo et al. showed that deciding whether $\vec{\chi}(G) \le k$ can be solved in $O(2^{t^2} \cdot k^{3t} \cdot t \cdot n)$ time in the class of $n$-vertex graphs with treewidth at most $t$. In other words, the problem is FPT parameterized by the treewidth of $G$ plus the value $k$ of the solution. Moreover, they showed that the weighted version of this problem (when edges of the input graph $G$ have weights given as input) is W[1]-hard when parameterized only by the treewidth. For semi-proper orientation, Dehgan and Havet [14] proved that deciding whether $\vec{\chi}_s(G) = \vec{\chi}(G)$ is NP-complete, even if $G$ is planar and $\vec{\chi}_s(G) = 2$, and that deciding whether $\vec{\chi}_s(G) \le 2$ is also NP-complete even if $G$ is planar and bipartite.

**Our contributions.** In Section 2, we present some definitions that we need along the text. Then, in Section 3, we prove that $\vec{\chi}_s(G) \in \{\omega(G) - 1, \omega(G)\}$ for every split graph $G$, and that, given a split graph $G$, deciding whether $\vec{\chi}_s(G) = \omega(G) - 1$ is an NP-complete problem. Note that, in contrast, $\vec{\chi}(G) \le 2\omega(G) - 2$ for every split graph $G$ and that this bound is tight [4]. To conclude Section 3, we show that, for every $k$, there exists a chordal graph $G$ and a split subgraph $H$ of $G$ such that $\vec{\chi}(G) \le k$ and $\vec{\chi}(H) = 2k - 2$. In Section 4, we show that $\vec{\chi}_s(P_n^p) = \lceil \frac{3}{2}p \rceil$ for every $n \ge p(p+1)$, where $P_n^p$ is the $p^{th}$ power of the path on $n$ vertices. Since $\vec{\chi}_s$ is monotone, this implies that $\vec{\chi}_s(G) \le \lceil \frac{3}{2}(\omega(G) - 1) \rceil$ for any unit interval graph $G$, and that this bound is tight. On the other hand, since $\vec{\chi}$ is not monotone, we investigate further unit interval graphs with small clique number: we show that $\vec{\chi}(G) \le 3$ for any unit interval graph $G$ with $\omega(G) = 3$ and, through a complete characterization of unit interval graphs with $\vec{\chi}(G) = \omega(G) = 3$, we design a linear-time algorithm that computes $\vec{\chi}(G)$ in this class of graphs. In Section 5, we show that deciding whether $\vec{\chi}_s(G) = \omega(G)$ can be solved in polynomial time in the class of co-bipartite graphs. Finally, in Section 6, we show that computing $\vec{\chi}_s(G)$ is FPT when parameterized by the minimum size of a vertex cover in $G$ or by the treewidth of $G$. As corollaries, we obtain kernels of size $4^{\mathcal{O}(k^2)}$ and $\mathcal{O}(2^k k^2)$, in chordal graphs and split graphs respectively, for the problem of deciding whether $\vec{\chi}_s(G) \le k$ parameterized by $k$. We also show that this problem does not admit a polynomial kernel in the class of chordal graphs, unless NP $\subseteq$ coNP/poly. We also prove that not only computing $\vec{\chi}_s(G)$, but also $\vec{\chi}(G)$, admits a polynomial kernel when parameterized by the neighbourhood diversity plus the value of the solution. While the complexity of computing $\vec{\chi}$ and $\vec{\chi}_s$ is open in cographs [4], we present exponential kernels for both problems parameterized by the value of the solution when restricted to cographs. We conclude with several open questions in Section 7.

## 2 Definitions

We denote by $[n]$ the set of first $n$ positive integers $\{1, \dots, n\}$. Each graph $G$ in this work is **simple**, i.e. there are no parallel edges nor loops. Thus, we consider edges as subsets of two distinct vertices, and we use $uv$ to denote an edge, as a shorthand for $\{u, v\}$. Given a graph $G$, we use $V(G)$ and $E(G)$ to denote its vertex set and edge set, whose cardinalities are known as the **order** and **size** of $G$, and are denoted by $n(G)$ and $m(G)$, respectively.

Given two subsets $A$ and $B$ of vertices, we denote by $E(A, B)$ the set of edges having one end in $A$ and the other in $B$. The **neighbourhood** of a vertex $v \in V(G)$ in a graph $G$ is denoted by $N_G(v) = \{u \mid uv \in E(G)\}$ and, since $G$ is an undirected simple graph, the **degree** of $v$ in $G$ is $d_G(v) = |N_G(v)|$. Subscripts will be omitted when $G$ is clear from the context. Two vertices $u$ and $v$ in a graph $G$ are **twins** if $N_G(u) = N_G(v)$. We denote by $\delta(G)$ and $\Delta(G)$ the minimum and maximum degree of a vertex in $G$, respectively.

A graph $H$ is a **subgraph** of $G$ if $V(H) \subseteq V(G)$ and $E(H) \subseteq E(G)$, in which case we also say that $G$ is a **supergraph** of $H$. When $S \subsetneq V(G)$, the graph $G-S$ is obtained from $G$ by the removal of all vertices in $S$ and all the edges that are incident to at least one vertex in $S$. A subgraph $H$ of $G$ is a **subgraph induced** by $S \subseteq V(G)$, denoted as $H = G[S]$, if $H = G - (V(G) \setminus S)$.

A **clique** in $G$ is a set of pairwise adjacent vertices. The cardinality of a largest clique in $G$ is called the **clique number** of $G$ and denoted by $\omega(G)$. A **stable** (a.k.a. **independent**) set in $G$ is a set of pairwise
non-adjacent vertices in $G$. The cardinality of a largest stable set in $G$ is called the **stability number** of $G$ and denoted by $\alpha(G)$. A graph $G$ whose vertex set is itself a clique is called **complete**.

A $(u, v)$-path on $k$ vertices in a graph $G$ is a sequence $P_k = (u = v_1, e_1, v_2, e_2, \dots, e_{k-1}, v_k = v)$ satisfying $e_i = v_i v_{i+1} \in E(G)$ for every $i \in \{1, \dots, k-1\}$, and $v_i \neq v_j$ for every $1 \le i \neq j \le k$. A $(u, v)$-path $P$ in $G$ is **Hamiltonian** if $P$ traverses/contains all vertices of $G$. A graph $G$ is **connected** if there exists a $(u, v)$-path in $G$ for any $u, v \in V(G)$. A **cycle** on $k$ vertices in $G$ is a sequence $C_k = (u = v_1, e_1, v_2, e_2, \dots, e_{k-1}, v_k = u)$ satisfying $e_i = v_i v_{i+1} \in E(G)$ for every $i \in \{1, \dots, k-1\}$, and $v_i \neq v_j$ for every $1 \le i \neq j \le k-1$. A graph $G$ is **chordal** if every cycle $C_k$ in $G$ such that $k \ge 4$ has a **chord**, i.e., an edge linking two non-consecutive vertices of $C_k$. We do the usual abuse of notation of referring to the subgraph (and not the sequence) of $G$ corresponding to a path or a cycle by the same nomenclature.

A **matching** in $G$ is a set of pairwise non-intersecting (i.e., with no end in common) edges. An **anti-matching** is a set of pairwise non-intersecting pairs of non-adjacent vertices. In other words, it is a matching in the complement of $G$. Let $M$ be a matching or an anti-matching. For every edge $uv$ of $M$, we say that $u$ is **matched with** $v$ by $M$, and write $u = M(v)$ and $M(u) = v$. We say that $M$ **saturates** a set of vertices $A$ if every vertex $a \in A$ is matched by $M$.

Similarly, each directed graph $D = (V, A)$ in this work is **simple**, i.e., has no parallel arcs, no symmetric arcs, and no loops. Given a digraph $D$, we use $V(D)$ and $A(D)$ to denote its vertex set and arc set; and $n(D)$ and $m(D)$ to denote their cardinalities, respectively. If $(u, v) \in A(D)$ is an arc in $D$, the **tail** of $(u, v)$ is $u$ and its **head** is $v$. Let $v$ be a vertex of $D$. The **out-neighbourhood** of $v$, denoted by $N_D^+(v)$, is the set of vertices $u$ such that $(v, u) \in A(D)$. The **in-neighbourhood** of $v$, denoted by $N_D^-(v)$, is the set of vertices $u$ such that $(u, v) \in A(D)$. The **out-degree** $d_D^+(v)$ (resp. the **in-degree** $d_D^-(v)$) of $v$ is $|N_D^+(v)|$ (resp. $|N_D^-(v)|$). The notions of (Hamiltonian) path, cycle, (induced) subgraph, have their straightforward notions in digraphs called as (resp. **Hamiltonian**) **directed path**, **directed cycle**, **(induced) subdigraph**. For any $W \subseteq V(D)$, we denote by $D\langle W \rangle$ the **subdigraph induced by** $W$ in $D$, and we denote by $D - W$ the digraph $D\langle V(D) \setminus W \rangle$.

A **tournament** $T$ is an orientation of a complete graph $G$. A **regular tournament** $T$ is a tournament where $d^-(v) = d^+(v)$ for every vertex $v \in V(T)$. A **transitive tournament** $T$ is a tournament such that if $(u, v), (v, w) \in A(T)$, then $(u, w) \in A(T)$, for every $u, v, w \in V(T)$.

### 3 Split graphs

A **split graph** is a graph whose vertex set can be partitioned into a clique and a stable set. A **split partition** of a split graph $G$ is a bipartition $(K, S)$ of $V(G)$ where $K$ is a clique and $S$ is a stable set.

**Theorem 3.1.** If $G$ is a connected split graph, then $\vec{\chi}_s(G) \in \{\omega(G) - 1, \omega(G)\}$.

*Proof.* Let $G$ be a split graph. We have $\vec{\chi}_s(G) \ge \chi(G) - 1 = \omega(G) - 1$.

Let $(K, S)$ be a split partition of $G$ with $K = \{v_1, \dots, v_k\}$. Let $D$ be the orientation of $G$ such that $D\langle K \rangle$ is a transitive tournament with Hamiltonian directed path $(v_1, \dots, v_k)$ and all the edges between $K$ and $S$ are oriented towards $S$. Let $w$ be an arc-weighting of $D$ such that every arc of $D\langle K \rangle$ has weight 1, and every vertex in $S$ has in-weight $\omega(G)$. Such an arc-weighting exists because $d_D^-(v) \le |K| \le \omega(G)$ for all $v \in S$. For every $i \in [k]$, we have $S_{(D,w)}(v_i) = i - 1 < k = \omega(G)$. Hence $(D, w)$ is a semi-proper orientation of $G$, so $\vec{\chi}_s(G) \le \omega(G)$. $\square$

A natural question that arises with Theorem 3.1 is whether one can decide in polynomial time if $\vec{\chi}_s(G) = \omega(G) - 1$. We show in the sequel that this is not possible unless $P = NP$.

**Theorem 3.2.** It is NP-complete to decide whether a given split graph $G$ has semi-proper orientation number equal to $\omega(G) - 1$.

*Proof.* We reduce the well-known 3-SAT problem to ours. Let $\Phi$ be a 3-SAT formula with $n$ variables $x_1, \dots, x_n$ and $m$ clauses $C_1, \dots, C_m$. In addition, we assume that each clause has exactly three literals.
We construct the split graph $G_{\Phi}$ as follows: We create a clique $K$ of size $4n-3$ which is the disjoint union of $\{x_0\} \cup \bigcup_{i \in [n]} \{x_i, \bar{x}_i\}$ and two sets $D$ and $D'$ of size $n-2$. We create a stable set $S$ of size $2n+m+1$ which is the disjoint union of $\{y_0\} \cup \bigcup_{i \in [n]} \{y_i, y'_i\}$ and $\{C_j \mid j \in [m]\}$.

We then add edges between $K$ and $S$ as follows:

* we link $y_0$ to all vertices of $K$ except $x_0$;

* for every $i \in [n]$, we connect $y_i$ to all vertices of $K$ except $x_i, \bar{x}_i$ and $i-1$ vertices in $D$, and we connect $y'_i$ to all vertices of $K$ except $x_i, \bar{x}_i$ and $i-1$ vertices in $D'$;

* for every $j \in [m]$, we connect the clause $C_j$ to all vertices of $K$ except its three literals and $n-2$ vertices in $D \cup D'$.

By construction $K$ is a maximum clique of $G$ so $\omega = \omega(G) = 4n-3$. We shall prove that $\vec{\chi}_s(G) = \omega-1$ if and only if $\Phi$ is satisfiable.

Assume first that $G$ admits a semi-proper weighted orientation $(D, w)$ with maximum in-weight $\omega-1$. Since $K$ is a clique of size $\omega$, for every $k \in \{0, \dots, \omega-1\}$ there is exactly one vertex of $K$ with in-weight $k$. Thus $D\langle K\rangle$ is a transitive tournament, all the arcs of $D\langle K\rangle$ have weight 1, and all edges in $E(K, S)$ are oriented towards their end in $S$.

Consider now $y_0$. We have $S_{(D,w)}(y_0) \ge d_D^-(y_0) = d_G(y_0) = \omega-1$. Hence $S_{(D,w)}(y_0) = \omega-1$ and so $x_0$ has also in-weight $\omega-1$, since $D$ is proper.

For every $i \in [n]$, let $z_i$ be the vertex of $K$ with in-weight $\omega-1-i$.

**Claim 3.2.1.** $z_i \in \{x_i, \bar{x}_i\}$ for every $i \in [n]$.

*Proof:* By induction on $i \in [n]$. Observe that both $y_i$ and $y'_i$ are adjacent to $\{x_0, \dots, x_{i-1}\}$. Thus, by the induction hypothesis and because $S_{(D,w)}(x_0) = \omega-1$, they are adjacent to a vertex with in-degree $\omega-1-k$ for every $k \in \{0, \dots, i-1\}$. But, by construction, $y_i$ and $y'_i$ have in-weight $\omega-1-i$ in $D$. Therefore, $S_{(D,w)}(y_i) = S_{(D,w)}(y'_i) = \omega-1-i$. Now $z_i$ is neither adjacent to $y_i$ nor $y'_i$ (in particular, $z_i \notin D \cup D'$). Hence, by construction, $z_i$ is either $x_i$ or $\bar{x}_i$.

<figure><img src="image_2.png" /></figure>

Let $\varphi$ be the truth assignment defined by $\varphi(x_i) = true$ if $x_i = z_i$ and $\varphi(x_i) = false$ if $z_i = \bar{x}_i$. This is well-defined by the above claim. Consider a clause $C_j = \ell_{i_1} \lor \ell_{i_2} \lor \ell_{i_3}$, with $\ell_{i_p} \in \{x_{i_p}, \bar{x}_{i_p}\}$ for all $p \in [3]$. It has degree $\omega-1-n$ in $G$ and so in-degree $\omega-1-n$ in $D$. Hence $s_j = S_{(D,w)}(C_j) \ge \omega-1-n$. Moreover, $C_j$ is adjacent to $x_0$. Thus, $s_j$ must be exactly the in-weight of one of the vertices corresponding to literals belonging to $C_j$ and so, by our definition of $\varphi$, $C_j$ is satisfied. Consequently, $\varphi$ satisfies $\Phi$.

Reciprocally, assume that there is a truth assignment $\varphi$ satisfying $\Phi$. Let $z_i = x_i$ if $\varphi(x_i) = true$ and let $z_i = \bar{x}_i$ if $\varphi(x_i) = false$. Orient $K$ in a transitive tournament such that $x_0$ has in-degree $\omega-1$ and $z_i$ has in-degree $\omega-1-i$ for all $i \in [n]$. Orient all the edges between $K$ and $S$ from $K$ to $S$. This results in the orientation $D$. Let us now assign weights on the arcs of $D$. All arcs with both end-vertices in $K$ are weighted by 1. For each $i \in [n]$, we assign weights to the arcs entering $y_i$ and $y'_i$ so that they both have in-weight $\omega-1-i$. For each $j \in [m]$, the clause $C_j$ has a literal which is true, so $C_j$ is non-adjacent to $z_{ij}$ for some $i_j \in [n]$. Hence we assign weights to the arcs entering $C_j$ so that $C_j$ has in-weight $\omega-1-i_j$. The resulting weighted orientation $(D, w)$ is a semi-proper orientation of $G$ with maximum in-weight $\omega-1$. $\square$

Let us now use Theorem 3.1 to argue that, for a given chordal graph $G$, one may find a subgraph $H \subseteq G$ such that $\vec{\chi}(H) \ge 2\vec{\chi}(G) - 2$.

**Proposition 3.3.** Every graph $H$ has a supergraph $G$ such that $\vec{\chi}(G) \le \vec{\chi}_s(H)$.

*Proof.* Let $H$ be a graph, and $(D, w)$ be an optimal semi-proper orientation of $H$. Let $G$ be the graph obtained from $H$ by adding for each vertex $v \in V(H)$ a set $S_v$ of $S_{(D,w)}(v) - d_D^-(v)$ new vertices of degree 1 adjacent to $v$, and let $D'$ be the orientation of $G$ obtained from $D$ by orienting all the edges between the new vertices and $V(H)$ towards $V(H)$. Every new vertex is a source in $D'$ and, by the construction of $G$, we have that $S_{(D,w)}(v) = d_{D'}^-(v)$. Therefore, $D'$ is a proper orientation of $G$ with maximum in-degree equal to $\vec{\chi}_s(H)$. $\square$
Observe that, if the graph $H$ is chordal (resp. a tree), then the supergraph $G$ given by the proof of Proposition 3.3 is also chordal (resp. a tree). Araujo et al. [4] proved that there exists a split graph $H$ such that $\vec{\chi}(H) = 2\omega(H) - 2$. Hence with Theorem 3.1, this implies the following.

**Corollary 3.4.** For every $k$, there exists a (chordal) graph $G$ and a (split) subgraph $H$ of $G$ such that $\vec{\chi}(G) \le k$ and $\vec{\chi}(H) = 2k - 2$.

**Problem 3.5.** Does there exist a function $\theta$ such that $\vec{\chi}(H) \le \theta(\vec{\chi}(G))$ for every graph $G$ and every subgraph $H$ of $G$?

# 4 Unit interval graphs

A graph $G$ is an **interval graph** if it can be obtained from a set of intervals on the real line, by adding a vertex for each interval, and adding an edge for each pair of vertices whose intervals intersect. It is the **intersection graph** of the intervals. A **unit interval graph** $G$ is an interval graph that can be obtained from intervals on the real line of that are of the same length.

If $G$ is a unit interval graph, then $\Delta(G) \le 2\omega(G) - 2$, so by Equation (2), we get the following.

**Proposition 4.1.** If $G$ is a unit interval graph, then $\vec{\chi}_s(G) \le \vec{\chi}(G) \le 2\omega(G) - 2$.

A unit interval graph with clique number 2 is the disjoint union of paths. It is easy to check that a path of order at least 4 has (semi-)proper orientation number equal to 2.

Let $P_n^k$ be the $k$-th power of the path of order $n$, i.e., the graph with vertex set $\{v_1, \dots, v_n\}$ and edge set $\{v_i v_j \mid i - j \in [k]\}$. The following proposition is easy to prove and well known.

**Proposition 4.2.** Every unit interval graph of order $n$ with clique number at most $\omega$ is a subgraph of $P_n^{\omega-1}$.

So, let us present our result on powers of paths.

**Proposition 4.3.** Let $b$ and $\omega$ be positive integers such that $b > \omega$, and let $n = b \times \omega$. Then $\vec{\chi}_s(P_n^{\omega-1}) = \vec{\chi}(P_n^{\omega-1}) = \lceil \frac{3}{2}(\omega - 1) \rceil$.

*Proof.* For every $i \in [b]$, let $C_i = \{v_j \mid (i-1)\omega + 1 \le j \le i \cdot \omega\}$. Observe that each $C_i$ is a clique.

Let $(D, w)$ be a semi-proper weighted orientation of $P_n^{\omega-1}$ and let $k$ be its maximum in-weight. Therefore all vertices of $C_i$ have different in-weights and so

$$ \sum_{v \in V(G)} S_{(D,w)}(v) = \sum_{i \in [b]} \sum_{v \in C_i} S_{(D,w)}(v) \le b(k + k - 1 + \dots + k - \omega + 1) = b \cdot \omega \left(k - \frac{1}{2}(\omega - 1)\right) \quad (4) $$

But

$$ \sum_{v \in V(G)} S_{(D,w)}(v) \ge \sum_{v \in V(G)} d_D^-(v) \ge |E(G)| = n(\omega - 1) - \frac{1}{2}\omega(\omega - 1) = b \cdot \omega \left(\omega - 1 - \frac{\omega - 1}{2b}\right). \quad (5) $$

Equations (4) and (5) (divided by $b \cdot \omega$) yield

$$ k \ge \frac{3}{2}(\omega - 1) - \frac{\omega - 1}{2b} > \frac{3}{2}(\omega - 1) - \frac{1}{2}. $$

Since $k$, $b$ and $\omega$ are integers, we have $k \ge \lceil \frac{3}{2}(\omega - 1) \rceil$.

Consequently, $\vec{\chi}_s(P_n^{\omega-1}) \ge \lceil \frac{3}{2}(\omega - 1) \rceil$.

Let us now prove that $\vec{\chi}(P_n^{\omega-1}) \le \lceil \frac{3}{2}(\omega - 1) \rceil$. We distinguish two cases depending on whether $\omega$ is odd or even.
* Assume first that $\omega$ is odd. Take an orientation $D$ of $G$ such that for every $i \in [b-1]$, all edges in $E(C_{i+1}, C_i)$ are oriented towards $C_i$, $D\langle C_b \rangle$ is a transitive tournament with Hamiltonian directed path $(v_{n-\omega+1}, \dots, v_n)$, and for every $i \in [b-1]$, $D\langle C_i \rangle$ is a regular tournament.

For every $j \in [\omega]$, we have $d_D^-(v_{(b-1)\omega+j}) = j-1$. For every $i \in [b-1]$ and every $j \in [\omega]$, the vertex $v_{(i-1)\omega+j}$ has $\frac{\omega-1}{2}$ in-neighbours in $C_i$ and $j-1$ in-neighbours in $C_{i+1}$. Hence $d_D^-(v_{(i-1)\omega+j}) = \frac{\omega-1}{2} + j - 1$. Consequently $D$ is a proper orientation of $D$ with maximum in-degree $\frac{3}{2}(\omega-1)$.

* Assume now that $\omega$ is even. Take an orientation $D$ of $G$ such that for every $i \in [b-1]$, all edges in $E(C_{i+1}, C_i)$ are oriented towards $C_i$, $D\langle C_b \rangle$ is a transitive tournament with Hamiltonian directed path $(v_{n-\omega+1}, \dots, v_n)$, and for every $i \in [b-1]$, $D\langle C_i \rangle$ is a quasi-regular tournament such that, for every $1 \le j \le \frac{\omega}{2}$, $v_{(i-1)\omega+j}$ has in-degree $\frac{\omega-2}{2}$ and for every $\frac{\omega}{2}+1 \le j \le \omega$ $v_{(i-1)\omega+j}$ has in-degree $\frac{\omega}{2}$.

For every $j \in [\omega]$, the vertex $d_D^-(v_{(b-1)\omega+j}) = j-1$. Let $i \in [b-1]$ and $j \in [\omega]$. Since $v_{(i-1)\omega+j}$ has $j-1$ in-neighbours in $C_{i+1}$, it follows that and $d_D^-(v_{(i-1)\omega+j}) = \frac{\omega-2}{2} + j - 1$ if $1 \le j \le \frac{\omega}{2}$, and $d_D^-(v_{(i-1)\omega+j}) = \frac{\omega}{2} + j - 1$ if $\frac{\omega}{2} + 1 \le j \le \omega$. Consequently $D$ is a proper orientation of $D$ with maximum in-degree $\frac{3}{2}\omega - 1 = \lceil \frac{3}{2}(\omega-1) \rceil$.

□

In the sequel, we prove (in Lemma 4.4) that if $G$ is an unit interval graph with clique number 3, then $\vec{\chi}_s(G) \le \vec{\chi}(G) \le 3$. Moreover, we prove that if $\omega(G) \le 3$, then one can decide in linear time whether $\vec{\chi}(G) = 2$ (in Lemma 4.6). Overall, this gives a linear time algorithm that computes $\vec{\chi}(G)$ in the class of unit interval graph $G$ with $\omega(G) = 3$ (Theorem 4.7).

It is easy to check that every connected unit interval graph of order $n$ contains $P_n$ as a subgraph. Moreover, every unit interval graph $G$ with $\omega(G) \le 3$ is a subgraph of $P_n^2$. Let us start with a result on proper 3-orientations of such graphs.

**Lemma 4.4.** Let $P_n = (v_1, \dots, v_n)$ be an $n$-node path and $G$ be a graph such that $P_n \subseteq G \subseteq P_n^2$, for $n \ge 2$. Then, $G$ admits a proper 3-orientation $D$ such that $d_D^-(v_1) \le 1$, $d_D^-(v_2) \le 2$ and $d_D^-(v_n) \le 1$.

*Proof.* A **nice** orientation of $G$ is a proper 3-orientation of $G$ such that $d_D^-(v_1) \le 1$, $d_D^-(v_2) \le 2$ and $d_D^-(v_n) \le 1$.

We shall prove by induction on the number $n$ of vertices of $G$ that $G$ admits a nice orientation.

If $n \le 4$, then $\vec{\chi}(G) \le \Delta(G) \le 3$. So $G$ admits a proper 3-orientation. If $G$ is a path, then this orientation is necessarily nice. If $G$ is not a path, then it is one of the graphs whose nice orientation is depicted in Figure 1.

<figure><img src="image_3.png" /><figcaption>Figure 1: Nice orientations when $n \le 4$.</figcaption></figure>

Thus, assume $n \ge 5$ and any graph $H$ such that $P_k \subseteq H \subseteq P_k^2$ with $1 \le k < n$ has a nice orientation. Let $G$ be a graph such that $P_n \subseteq G \subseteq P_n^2$.

We shall show a nice orientation of $G$. We distinguish several cases. In order to shorten the writing, in all cases the orientation is explicitly shown and thus one can verify that the constraints $d_D^-(v_1) \le 1$ and
$d_D^-(v_2) \le 2$ are satisfied. The fact that $d_D^-(v_n) \le 1$ will always be a consequence of the induction hypothesis. Therefore we shall only explicitly check that the orientation is proper.

1. $d(v_2) = 2$ and $d(v_3) = 2$.

In this case, we extend a nice orientation $D_3$ of $G - \{v_1, v_2, v_3\}$ into a nice orientation $D$ of $G$ as depicted in Figure 2. This orientation is proper since $d_D^-(v_4) = d_{D_3}^-(v_4) \le 1$ because $D_3$ is nice.

<figure><img src="image_4.png" /><figcaption>Figure 2: The case $d(v_2) = 2$ and $d(v_3) = 2$.</figcaption></figure>

2. $d(v_2) = 2$ and $d(v_3) = 3$. If $v_1v_3 \in E(G)$, then we extend a nice orientation $D_3$ of $G - \{v_1, v_2, v_3\}$ into a nice orientation $D$ of $G$ as depicted in Figure 3. This orientation is proper since $d_D^-(v_4) = d_{D_3}^-(v_4) \le 1$ because $D_3$ is nice.

<figure><img src="image_5.png" /><figcaption>Figure 3: The case $d(v_2) = 2$, $d(v_3) = 3$ and $v_1v_3 \in E(G)$.</figcaption></figure>

If $v_3v_5 \in E(G)$, then we extend a nice orientation $D_2$ of $G - \{v_1, v_2\}$ into a nice orientation $D$ of $G$ as depicted in Figure 4. This orientation is proper since $d_D^-(v_3) = d_{D_2}^-(v_3) \le 1$, because $D_2$ is nice.

<figure><img src="image_6.png" /><figcaption>Figure 4: The case $d(v_2) = 2$, $d(v_3) = 3$ and $v_1v_3 \in E(G)$.</figcaption></figure>

3. $d(v_2) = 2$ and $d(v_3) = 4$. In this case, we extend a nice orientation $D_3$ of $G - \{v_1, v_2, v_3\}$ into a nice orientation $D$ of $G$ as in Figure 5. This orientation is proper since $d_D^-(v_4) = d_{D_3}^-(v_4) \le 1$ and $d_D^-(v_5) = d_{D_3}^-(v_5) \le 2$.

<figure><img src="image_7.png" /><figcaption>Figure 5: The case $d(v_2) = 2$ and $d(v_3) = 4$.</figcaption></figure>

4. $d(v_2) = 3$ and $d(v_3) = 2$. Let $D_4$ be a nice orientation of $G - \{v_1, v_2, v_3, v_4\}$. Depending on the degree of $v_4$ in $G$, extend it into a nice orientation $D$ of $G$ as depicted in Figure 6, ($d(v_4) = 3$ left and $d(v_4) = 4$ right). In both cases, $D$ is proper since $d_D^-(v_5) = d_{D_4}(v_5) \le 1$ and $d_D(v_6) = d_{D_4}(v_6) \le 2$ (in case $n \ge 6$) because $D_4$ is nice.
<figure><img src="image_8.png" /><figcaption>Figure 6: The case $d(v_2) = 3$ and $d(v_3) = 2$.</figcaption></figure>

5. $d(v_2) = 3$ and $d(v_3) = 3$.

If $v_1v_3 \in E(G)$, then we extend a nice orientation $D_3$ of $G - \{v_1, v_2, v_3\}$ into a nice orientation $D$ of $G$ as depicted in Figure 7. This orientation is proper since $d_D^-(v_4) = d_{D_3}^-(v_4) \le 1$ because $D_3$ is nice.

<figure><img src="image_9.png" /><figcaption>Figure 7: The case $d(v_2) = 3$, $d(v_3) = 3$ and $v_1v_3 \in E(G)$.</figcaption></figure>

If $v_3v_5 \in E(G)$, then we extend a nice orientation $D_3$ of $G - \{v_1, v_2, v_3\}$ into a nice orientation $D$ of $G$ as depicted in Figure 8. This orientation is proper since $d_D^-(v_4) = d_{D_3}^-(v_4) \le 1$ and $d_D^-(v_5) = d_{D_3}^-(v_5) \le 2$ because $D_3$ is nice.

<figure><img src="image_10.png" /><figcaption>Figure 8: The case $d(v_2) = 3$, $d(v_3) = 3$ and $v_3v_5 \in E(G)$.</figcaption></figure>

6. $d(v_2) = 3$ and $d(v_3) = 4$. In this case, we extend a nice orientation $D_3$ of $G - \{v_1, v_2, v_3\}$ into a nice orientation $D$ of $G$ as depicted in Figure 9. This orientation is proper since $d_D^-(v_4) = d_{D_3}^-(v_4) \le 1$ and $d_D^-(v_5) = d_{D_3}^-(v_5) \le 2$ because $D_3$ is nice.

<figure><img src="image_11.png" /><figcaption>Figure 9: The case $d(v_2) = 3$ and $d(v_3) = 4$.</figcaption></figure>

<figure><img src="image_12.png" /></figure>

The proof of Lemma 4.4 is constructive. That is, given a unit interval graph $G$ with clique number at most 3, it allows to build a proper orientation with proper orientation number at most 3. Recall that $\vec{\chi}(H) \ge \omega(H) - 1$ for any graph $H$, and so $\vec{\chi}(G) \in \{2, 3\}$. A simple dynamic programming algorithm would allow to decide whether $\vec{\chi}(G) = 2$, as the one presented in [7] for graphs of bounded treewidth. To conclude this section, we provide a full characterization of unit interval graphs with clique number 3 and with proper orientation number 2, which leads to a simpler algorithm.

As noticed in [4]:

**Proposition 4.5.** Let $G$ be any graph with $\vec{\chi}(G) = \omega(G) - 1$. Then, for any optimal proper orientation $D$ and any maximum clique $K$ of $G$, we have:
(a) the orientation $D$ restricted to $K$ induces a transitive tournament;

(b) $\{d_D^-(v) | v \in V(K)\} = \{0, \dots, \omega(G) - 1\}$; and

(c) for every $u \in V(K)$ and $v \notin V(K)$, $uv \in A(D)$.

Thus, if $K'$ is another maximum clique of $G$, $\{d_D^-(v) | v \in V(K) \cap V(K')\} = \{0, \dots, |V(K) \cap V(K')| - 1\}$.

Now, let us present a characterization of unit interval graphs with $\omega(G) = 3$ and $\vec{\chi}(G) = 2$.

**Lemma 4.6.** Let $G = (V, E)$ be a connected unit interval graph with $\omega(G) = 3$. Then, $\vec{\chi}(G) = 2$ if and only if $G$ has no induced subgraph isomorphic to one of the graphs depicted in Figure 10.

<figure><img src="image_13.png" /><figcaption>Figure 10: List of forbidden induced subgraphs for a unit interval graph $G$ with $\omega(G) = 3$ and $\vec{\chi}_s(G) = 2$.</figcaption></figure>

*Proof.* Recall, by Lemma 4.4 and the fact that $\vec{\chi}(G) \ge \omega(G) - 1$ for any graph, $\vec{\chi}(G) \in \{2, 3\}$.

Let us first prove that if one of the induced subgraphs in Figure 10 appears in $G$, then $\vec{\chi}(G) = 3$. Towards a contradiction, suppose that $\vec{\chi}(G) = 2$. Let $D$ be a proper 2-orientation of $G$.

Note that every triangle (clique of size three) in $G$ contains exactly 1 vertex of in-degree 0 in $D$. For any three triangles $K, K', K''$ in $G$ such that $K \cap K' \ne \emptyset$ and $K \cap K'' \ne \emptyset$, by Proposition 4.5, there is $K \cap K' \cap K'' \ne \emptyset$. Therefore, $G$ does not contain any of the graphs in Figures 10b and 10c.

Moreover, it is easy to check that, since $G$ is a unit interval graph and $K \cap K' \cap K'' \ne \emptyset$, we have that $G$ contains the graph in Figure 10a, and the middle vertex of the path is of in-degree 0 in $D$. But, as it is easy to check, there exists no proper 2-orientation of the graph in Figure 10a with the middle vertex of in-degree 0. A contradiction.

By Proposition 4.5, in any proper 2-orientation of $G$, any edge $xy$ with $x$ in a triangle and $y$ not in this triangle must be oriented from $x$ to $y$. Therefore, if $G$ contains the induced subgraph depicted in Figure 10d, there is no way to orient the edge between the two triangles in a proper 2-orientation of $G$.
Now, if $G$ contains an induced diamond $H$ (two triangles intersecting on an edge) as subgraph, there exists only one way (up to symmetry) to orient it in a proper way respecting that $\vec{\chi}(G) = 2$. See Figure 11. In particular, the two vertices $x$ and $y$ that do not belong to the intersection of the triangles must have in-degree 2 and the edges between $x$ (resp., $y$) and vertices not in $V(H)$ must be oriented from $x$ (resp., from $y$). It can be checked that there is no way to extend this orientation in the graphs of Figures 10e to 10h while keeping $\vec{\chi}(G) = 2$.

<figure><img src="image_14.png" /><figcaption>Figure 11: Single proper orientation (up to symmetry of the central edge) of a diamond subgraph of a graph $G$ with $\vec{\chi}(G) = 2$.</figcaption></figure>

Now, let us show that any unit interval graph $G$ with $\omega(G) = 3$ and with no induced subgraphs of Figure 10 satisfies $\vec{\chi}(G) = 2$.

Let $P = (v_1, \dots, v_n)$ be such that $G$ is a subgraph of $P^2$.

Let $X \subseteq V$ be the set of vertices not in any triangle. Let $B_1, \dots, B_r$ be the connected components (called *blocks*) of $G-X$, in the order they appear in $P$ (i.e., for any $v_o \in B_i$ and $v_p \in B_j$ with $i < j$, then $o < k$). Note that, by the assumption, each $B_i$ is isomorphic to some graph depicted in Figure 12.

<figure><img src="image_15.png" /><figcaption>Figure 12: Possible blocks.</figcaption></figure>

Let $Q_1, \dots, Q_\ell$ be the maximal subpaths with at least two vertices of $P$ with internal vertices not in any triangle (note that the end of these paths may belong to some triangle) in the order they appear in $P$ (note that $r-1 \le \ell \le r+1$). If $v_1 \in V(B_1)$ (in which case $\ell \le r$), we set $P_1 = \{v_1\}$ and $P_i = Q_{i-1}$ for every $2 \le i \le \ell+1$, and otherwise, $P_i = Q_i$ for every $1 \le i \le \ell$. If $v_n \in B_r$ (in which case $\ell \le r$), we set $P_{r+1} = \{v_n\}$. Note that the $P_i$'s are pairwise vertex-disjoint and that, for every $1 < i \le r$, $|V(P_i)| \ge 3$ (because of the forbidden induced subgraph depicted in Figure 10d), and $|V(P_1)|, |V(P_{r+1})| \ne 3$ (because of the forbidden induced subgraph depicted in Figure 10e). Moreover, note that, for every $1 \le i \le r$, $B_i$ intersects $P_i$ in one vertex, denoted by $l_i$ (the “left” vertex of $B_i$ and the “right” end of $P_i$), and $P_{i+1}$ in one vertex, denoted by $r_i$ (the “right” vertex of $B_i$ and the “left” end of $P_{i+1}$).

Let $r$ be the number of blocks. Note that $r \ge 1$ since $\omega(G) = 3$. We show by induction on $1 \le j \le r$, that:

* if $B_j$ is a diamond, then there exists a proper 2-orientation of $Y_j = \bigcup_{1 \le i \le j} G[P_i \cup B_i]$ such that $r_j$ has in-degree 2;

* otherwise, there are two proper 2-orientations of $Y_j$ one in which $r_j$ has in-degree 1 and another such that $r_j$ has in-degree 2.
Furthermore, we also prove that when $j = r$, then one can extend a proper 2-orientation of $Y_r$ to $G$.

If $B_1$ is a diamond, let us orient $P_1$ (if $P_1 \neq \{v_1\}$) in such a way that $l_1$ has in-degree 0 (in $P_1$), and the neighbour of $l_1$ has in-degree different than 2 (looking at Figure 13, it is possible since the length of $P_1$ is not 2 by assumption). Then, orient $B_1$ as in Figure 14b, so that $r_1$ has in-degree 2. If $B_1$ is a single triangle or two triangles intersecting in one vertex, let us give to $P_1$ (if $P_1 \neq \{v_1\}$) any orientation given in Figure 13 (so $l_1$ has in-degree 0) and then: if $B_1$ is one triangle, then orient $B_1$ in such a way that $l_1$ has in-degree 0 (Figure 14a, and, if $B_1$ consists of two triangles intersecting in one vertex, then orient $B_1$ in such a way that $l_1$ has in-degree 2 (Figure 14c). In both cases, there are two possible such orientations, one leading $r_1$ with in-degree 1 and the other with $r_1$ with in-degree 2 (see Figures 14a and 14c).

<figure><img src="image_16.png" /><figcaption>(a) Single possible orientations for paths of length at most 3 (up to left/right symmetry).</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>(b) Single possible orientations for paths of length 4. Note that no such orientation allows the two neighbours of the ends to have different in-degree.</figcaption></figure>

<figure><img src="image_18.png" /><figcaption>(c) Single possible orientations for paths of length 5 (up to symmetry). Note that no such orientation allows the two neighbours of the ends to have both in-degree 1.</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>(d) Possible orientations for paths of length $2\ell + 1$, for $\ell \ge 3$. Note that, it is possible to ensure that the neighbours of the ends have in-degree 1 or 2. The case $\ell = 2$ can be extended to any path of length $2\ell + 1$, $\ell \ge 3$, as follows. Let $uv \in E$ such that the in-degree of $u$ equals 0. Then subdivide twice $uv$ into a path $(u, x, y, v)$ with arcs $ux, xy$ and $vy$.</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>(e) Possible orientations for paths of length $2\ell$, for $\ell \ge 4$. Note that, it is possible to ensure that the neighbours of the ends have in-degree 1 or 2. The case $\ell = 4$ can be extended to any path of length $2\ell$, $\ell \ge 4$, as follows. Let $uv \in E$ such that the in-degree of $u$ equals 0. Then subdivide twice $uv$ into a path $(u, x, y, v)$ with arcs $ux, xy$ and $vy$.</figcaption></figure>

<caption>Figure 13: Orientations of paths such that both ends are sources (but in the case of the path of length one). Integers in the nodes refer to their in-degree.</caption>

Let us assume, by induction on $j$ where $1 \le j \le r$, that a proper 2-orientation of $Y_j = \bigcup_{1 \le i \le j} G[P_i \cup B_i]$
has been obtained for some $1 \le j \le r$, such that: if $B_j$ is a diamond, then $r_j$ has in-degree 2, and otherwise, we have both a proper 2-orientation of $Y_j$ such that $r_j$ has in-degree 1 and a proper 2-orientation of $Y_j$ such that $r_j$ has in-degree 2. Note that this is satisfied for $j = 1$ by the previous paragraph.

If $j = r$ and $P_{r+1} \ne \{v_n\}$ (as otherwise we already have a proper 2-orientation of $G$), then a proper 2-orientation of $P_{r+1}$ extending the one of $Y_r$ can be found according to Figure 13. Recall that, if $B_r$ is a diamond, then, by assumption, $P_{r+1}$ has length different than 2 and so the neighbour of $r_r$ in $P_{r+1}$ can be chosen with in-degree different than 2. Hence, one can obtain a proper 2-orientation of $G$.

<figure><img src="image_21.png" /><figcaption>(a) Possible orientations of $K_3$ (recall that the order of the vertices (from left to right) is the same as in $P$).</figcaption></figure>

<figure><img src="image_22.png" /><figcaption>(b) Single orientation of the diamond (up to reverse the central edge).</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>(c) Possible orientation of two triangles intersecting in one vertex (by Proposition 4.5, this common vertex must have in-degree 0).</figcaption></figure>

Figure 14: Possible proper 2-orientations of the blocks (where vertices are ordered from left to right as they appear in $P$).

Suppose then that $1 \le j < r$. There are several cases to consider depending whether $B_j$ and $B_{j+1}$ are diamonds or not.

* If $B_j$ and $B_{j+1}$ are not diamonds. Consider a proper 2-orientation of $Y_j$ such that $r_j$ has in-degree 1, which exists by induction hypothesis. Give to $P_{j+1}$ any orientation with the neighbour of its left end $r_{j+1}$ having in-degree $\ne 1$ (which exists as in Figure 13 since, by assumption, the length of $P_{j+1}$ is at least 2). Finally,

- if $B_{j+1}$ is a triangle, there are two possible orientations of $B_{j+1}$ such that $l_{j+1}$ has in-degree 0: one with $r_{j+1}$ with in-degree 1 and the other one with $r_{j+1}$ with in-degree 2 (see Figure 14a);

- otherwise $B_{j+1}$ consists of two triangles intersecting in one vertex, and then there are two possible orientations of $B_{j+1}$ such that $l_{j+1}$ has in-degree different from the left neighbour of $l_{j+1}$ in $P_{j+1}$: one with $r_{j+1}$ with in-degree 1 and the other one with $r_{j+1}$ with in-degree 2 (see Figure 14c).

* If $B_j$ is not a diamond and $B_{j+1}$ is a diamond. Orient $B_{j+1}$ as in Figure 14b and so $r_{j+1}$ and $l_{j+1}$ have both in-degree 2. Then, give to $P_{j+1}$ an orientation such that $l_{j+1}$ has in-degree 2. As shown in Figure 13, here there exists such orientation in which the right neighbour of $r_j$ has in-degree 1 or,
resp., 2 because $P_{j+1}$ has length 4 or larger than 6, by assumption. Then, it can be completed into a
proper orientation of $Y_{j+1}$ by using a proper 2-orientation of $Y_j$ such that $r_j$ has in-degree 2 or, resp.,
1 that exists by induction.

* If $B_j$ is a diamond and $B_{j+1}$ is not a diamond. Then, by induction, there exists a proper 2-orientation of $Y_j$ such that $r_j$ has in-degree 2. Then, orient $P_{j+1}$ using an orientation such that the neighbour of $r_j$ in $P_{j+1}$ has in-degree 1. Note that the in-degree of the left neighbour of $l_{j+1}$ is either 1 or 2 (see Figure 13). Then,

- if $B_{j+1}$ is a triangle, there are two possible orientations of $B_{j+1}$ such that $l_{j+1}$ has in-degree 0: one with $r_{j+1}$ with in-degree 1 and the other one with $r_{j+1}$ with in-degree 2 (see Figure 14a);

- otherwise $B_{j+1}$ consists of two triangles intersecting in one vertex and there are two possible orientations of $B_{j+1}$ such that $l_{j+1}$ has in-degree different from its left neighbour: one with $r_{j+1}$ with in-degree 1 and the other one with $r_{j+1}$ with in-degree 2 (see Figure 14c).

* If both $B_j$ and $B_{j+1}$ are diamonds. Then path $P_{j+1}$ between $B_j$ and $B_{j+1}$ is of length 4 or at least 6 by assumption. It is possible to orient it in such a way that the neighbours of $l_j$ and $r_{j+1}$ have in-degree different from 2 (see Figure 13). Therefore, we may orient $B_{j+1}$ as in Figure 14b such that we obtain a proper 2-orientation of $Y_{j+1}$ with $r_{j+1}$ with in-degree 2.

<figure><img src="image_24.png" /></figure>

So, we are ready to prove the main result of this section.

**Theorem 4.7.** For any unit interval graph $G$ with $\omega(G) = 3$, then $\vec{\chi}(G) \in \{2,3\}$. Moreover, there exists a linear-time algorithm to compute $\vec{\chi}(G)$.

*Proof.* The fact that $\vec{\chi}(G) \in \{2,3\}$ follows from the facts that $\vec{\chi}(G) \ge \omega(G) - 1$ for any graph $G$ and from Lemma 4.4. The linear complexity comes from the fact that computing a Hamiltonian path $P$ of $G$ such that $G$ is a subgraph of $P^2$ can be done in linear time [17], that the forbidden induced subgraphs and the blocks can be identified in linear time (by following the path $P$) and by Lemma 4.6. $\square$

The above section gives an ad-hoc proof that $\vec{\chi}(G) \le \omega(G)$ and an ad-hoc linear-time algorithm to compute $\vec{\chi}(G)$ for unit interval graphs with $\omega(G) = 3$. Similar results might be obtained by tedious case analysis for larger (but still constant) clique number. However, it would be interesting to obtain such general bound for all (unit) interval graphs. Recall that Proposition 4.3 provides a family of unit interval graphs with $\vec{\chi}(G) = \lceil \frac{3}{2}(\omega(G) - 1) \rceil$. Note that, in [11] (arXiv), it was stated that, for every graph $G$, $\vec{\chi}(G) = O\left(\frac{\chi(G) \log(\chi(G))}{\log \log \chi(G)}\right) + \frac{\mathrm{mad}(G)}{2}$. Supposing the provided proofs are correct, we obtain that, for any unit interval graph $G$, $\vec{\chi}(G) = O\left(\frac{\omega(G) \log(\omega(G))}{\log \log \omega(G)}\right) + \omega(G) - 1$, since, for any unit interval graph $G$, $\chi(G) = \omega(G)$ (since $G$ is a perfect graph) and $\mathrm{mad}(G) \le \mathrm{mad}(P_n^{\omega(G)}) \le 2(\omega(G) - 1)$.

Note that $\vec{\chi}(G)$ can be computed in linear time in interval graphs with bounded $\omega(G)$ by the dynamic programming for bounded treewidth graphs [7].

# 5 Cobipartite graphs

A graph is **cobipartite** if its vertex set has a partition $(K_1, K_2)$ such that both $K_1$ and $K_2$ are cliques. Such a partition is called a **cobipartition** of the graph. We assume for the remainder of the section that $K_1$ is the largest clique of a cobipartite graph $G$ with clique partition $\{K_1, K_2\}$ of $V(G)$.

The aim of this section is to prove the following theorem.

**Theorem 5.1.** *Given a cobipartite graph $G$ with cobipartition $(K_1, K_2)$, one can decide in polynomial time whether $\vec{\chi}_s(G) = |K_1| - 1$, assuming that $|K_1| = \max\{|K_1|, |K_2|\}$.*
To prove that $\vec{\chi}_s(G) = |K_1| - 1$, note that any optimal weighted orientation when restricted to $G[K_1]$ must be transitive with all weights equal to 1; and all edges from $K_1$ to $K_2$ must be oriented towards $K_2$. Thus, the goal in what follows it to decide which transitive orientation of $K_1$ to pick, how to assign weights to the edges from $K_1$ to $K_2$ and, overall, which weighted orientation to use in $K_2$ satisfying the upper bound of $|K_1| - 1$ and the constraints of being proper.

We need some preliminary results. Let $k_1$ and $k_2$ be two positive integers. Let $\vec{d} = (d_1, \dots, d_{k_2})$ be a sequence of non-negative integers. $\vec{d}$ is $k_1$-suitable if and only if there is a tournament $T$ with vertex set $\{v_1, \dots, v_{k_2}\}$ such that, for every $j \in [k_2]$, there are at most $j-1$ indices of $[k_2]$ such that $d_i + d_T^-(v_i) > k_1 - j$. Let us first characterize graphs with $\vec{\chi}_s(G) = k_1 - 1$.

**Lemma 5.2.** Let $G$ be a cobipartite graph $G$ with cobipartition $(K_1, K_2)$. Set $k_1 = |K_1|$ and $k_2 = |K_2|$, and let $K_2 = \{v_1, \dots, v_{k_2}\}$.

$\vec{\chi}_s(G) = k_1 - 1$ if and only if the two following statements hold:

(i) There exists an antimatching saturating $K_2$ in the bipartite graph induced by $E(K_1, K_2)$; and

(ii) There exists an ordering $(v_1, \dots, v_{k_2})$ of the vertices of $K_2$ such that $(d_{K_1}(v_1), \dots, d_{K_1}(v_{k_2}))$ is a $k_1$-suitable sequence.

*Proof.* Assume $\vec{\chi}_s(G) = k_1 - 1$. Let $(D, w)$ be an optimal semi-proper orientation of $G$. Set $T = D\langle K_2 \rangle$. Since $K_1$ is a clique, by Proposition 4.5, for each $i \in \{0, \dots, k_1\}$, there is exactly one vertex of $K_1$ with in-weight $i$, and all the edges of $E(K_1, K_2)$ are oriented towards $K_2$.

Now $K_2$ is also a clique, so the in-weights of its vertices are all distinct. For each $i \in [k_2]$, there is a unique vertex $u_i \in K_1$ such that $S_{(D,w)}(u_i) = S_{(D,w)}(v_i)$. Since $(D, w)$ is semi-proper, then $u_i$ and $v_i$ are not adjacent. Hence $M = \{u_i v_i \mid i \in [k_2]\}$ is an antimatching saturating $K_2$ in the bipartite graph induced by $E(K_1, K_2)$. So (i) holds.

Furthermore, since the in-weight of the $v_i$ are all distinct, there are at most $j-1$ vertices $v_i$ such that $S_{(D,w)}(v_i) \ge k_1 - j + 1$. But $S_{(D,w)}(v_i) \ge d_D^-(v_i) = d_{K_1}(v_i) + d_T^-(v_i)$. So there are at most $j-1$ vertices $v_i$ such that $d_{K_1}(v_i) + d_T^-(v_i) \ge k_1 - j + 1$. Hence $(d_{K_1}(v_1), \dots, d_{K_1}(v_{k_2}))$ is a $k_1$-suitable sequence, so (ii) holds.

Reciprocally, assume that (i) and (ii) hold. Let $T$ be an orientation of $K_2$ such that for every $j \in [k_2]$, there are at most $j-1$ indices of $[k_2]$ such that $d_i + d_T^-(v_i) > k_1 - j$. Free to relabel the vertices of $K_2$, we may assume that $d_{K_1}(v_1) + d_T^-(v_1) \ge d_{K_1}(v_2) + d_T^-(v_2) \ge \dots \ge d_{K_1}(v_{k_2}) + d_T^-(v_{k_2})$. Consequently, for every $i \in [k_2]$, $d_{K_1}(v_i) + d_T^-(v_i) \le k_1 - i$.

Let us construct a weighted orientation $D$ of $G$ as follows. First $D\langle K_2 \rangle = T$ and all the edges of $E(K_1, K_2)$ are oriented towards $K_2$. Let $i \in \{2, \dots, k_2\}$. Choose an arc $e_i$ of $A(T) \cup E(K_1, K_2)$ entering $v_i$; Such an arc exists since $d_{K_1}(v_i) + d_T^-(v_i) \ge d_{K_1}(v_{k_2}) + d_T^-(v_{k_2})$, and $d_{K_1}(v_i) + d_T^-(v_i) + d_{K_1}(v_{k_2}) + d_T^-(v_{k_2}) \ge |A(T\langle \{v_i, v_{k_2}\} \rangle)| \ge 1$; assign to all arcs entering $v_i$ a weight of 1 except for $e_i$ to which we assign weight $k_1 - i - (d_{K_1}(v_i) + d_T^-(v_i)) + 1$. Doing so, $S_{(D,w)}(v_i) = k_1 - i$ for all $i \in \{2, \dots, k_2\}$. Assign to all arcs entering $v_{k_2}$ a weight of 1. Then $S_{(D,w)}(v_{k_2}) = d_{K_1}(v_{k_2}) + d_T^-(v_{k_2}) \le k_1 - k_2$. Hence all the in-weights of the vertices of $K_2$ are distinct.

Now by (ii), there is an antimatching $M$ saturating $K_2$. Take a transitive orientation $T_1$ of $K_1$ such that $d_{T_1}^-(M(u_i)) = S_{(D,w)}(v_i)$ for all $i \in [k_2]$, and assign weight 1 to each of its arcs. One easily checks that the resulting weighted orientation of $G$ is semi-proper. $\square$

Let us now characterize $k_1$-suitable sequences.

**Lemma 5.3.** Let $k_1, k_2$ be two integers with $k_1 \ge k_2$, and let $\vec{d} = (d_1, \dots, d_{k_2})$ be a non-increasing sequence of non-negative integers. Then $\vec{d}$ is $k_1$-suitable if and only if there is a tournament $T$ with vertex set $\{v_1, \dots, v_{k_2}\}$ such that $d_i + d_T^-(v_i) \le k_1 - i$ for all $i \in [k_2]$.
*Proof.* By definition if there is a tournament $T$ with vertex set $\{v_1, \dots, v_{k_2}\}$ such that $d_i + d_T^-(v_i) \le k_1 - i$ for all $i \in [k_2]$, then $D$ is $k_1$-suitable.

Let us now prove the reciprocal. Assume that $\vec{d}$ is $k_1$-suitable. A tournament $T$ with vertex set $\{v_1, \dots, v_{k_2}\}$ is a $\vec{d}$-partner if for every $j \in [k_2]$, there are at most $j-1$ indices of $[k_2]$ such that $d_i+d_T^-(v_i) > k_1-j$. Observe that if $T$ is a $\vec{d}$-partner, then there is a permutation $\sigma$ of $[k_2]$ such that $d_i+d_T^-(v_i) \le k_1 - \sigma(i)$ for every $i \in [k_2]$. Such a permutation is an **adjoint** of $T$. The **displacement index** of $T$ of a permutation $\sigma$ of $[k_2]$ is the smallest index such that $\sigma(i) \neq i$ or $k_2+1$ of $\sigma$ is the identity.

Since $\vec{d}$ is $k_1$-suitable, by definition there is a $\vec{d}$-partner. Consider the pair $(T, \sigma)$ where $T$ is a $\vec{d}$-partner of $\vec{d}$ and $\sigma$ is an adjoint of $T$ that maximizes the displacement index of $\sigma$. We shall prove that $\sigma$ is the identity, and thus $d_i + d_T^-(v_i) \le k_1 - i$ for all $i \in [k_2]$.

Suppose, for a contradiction, that $\sigma$ is not the identity. Let $i$ be the displacement index of $\sigma$, and let $j = \sigma^{-1}(i)$. By definition, $j, \sigma(i) > i$, so $d_i \ge d_j$. We have

$$d_i + d_T^-(v_i) \le k_1 - \sigma(i) \le k_1 - i \\ d_j + d_T^-(v_j) \le k_1 - i$$

If $d_j + d_T^-(v_j) \le k_1 - \sigma_T(i)$, then the permutation $\sigma'$ defined by $\sigma'(i) = i$, $\sigma'(j) = \sigma(j)$ and $\sigma'(k) = \sigma(k)$ for all $k \in [k_2] \setminus \{i, j\}$, is also an adjoint of $T$ and has a larger displacement index than $\sigma$, a contradiction.

Henceforth, we may assume that $d_j + d_T^-(v_j) > k_1 - \sigma(i)$. Set $\alpha = d_j + d_T^-(v_j) - k_1 + \sigma(i)$. Observe that $v_j$ has $k_1 - \sigma(i) - d_j + \alpha$ in-neighbours in $T$ while $v_i$ has at most $k_1 - \sigma(i) - d_i \le k_1 - \sigma(i) - d_j$ in-neighbours in $T$. Therefore, there exists a set $A$ of $\alpha$ in-neighbours of $v_j$ which are not in-neighbours of $v_i$. Let $T'$ be tournament obtained from $T$ by reversing the direction of the arc between $a$ and $v_i$ and $v_j$ if $a \in A \setminus \{v_i\}$ and reversing the arc $v_iv_j$ if $v_i \in A$. All vertices distinct from $v_i$ and $v_j$ have same in-degree in $T'$ and $T$, while $d_{T'}(v_i) = d_T^-(v_i) + \alpha$ and $d_{T'}(v_j) = d_T^-(v_j) - \alpha$. Hence

$$d_i + d_{T'}^-(v_i) \le k_1 - \sigma(i) + \alpha = d_j + d_T^-(v_j) \le k_1 - i \\ d_j + d_{T'}^-(v_j) = d_j + d_{T'}^-(v_j) - \alpha = k_1 - \sigma(i)$$

Thus the permutation $\sigma'$ defined by $\sigma'(i) = i$, $\sigma'(j) = \sigma(j)$ and $\sigma'(k) = \sigma(k)$ for all $k \in [k_2] \setminus \{i, j\}$, is an adjoint of $T'$ and has a larger displacement index than $\sigma$, a contradiction. $\square$

**A score sequence** is a non-decreasing sequence of integers corresponding to the in-degrees of the vertices of a tournament. Let us recall a characterization of score sequences by Landau [22].

**Theorem 5.4** (Landau [22]). Let $\vec{s} = (s_1, \dots, s_n)$ be a non-decreasing sequence of non-negative integers. Then, $\vec{s}$ is a score sequence if and only if $\sum_{i=1}^n s_i = \binom{n}{2}$, and $\sum_{i=1}^k s_i \ge \binom{k}{2}$ for all $k \in [n]$.

With the following two corollaries, we will get an algorithmic tool for checking if a sequence is $k_1$-suitable.

**Corollary 5.5.** Let $\vec{s} = (s_1, \dots, s_n)$ be a non-decreasing sequence of non-negative integers. There is a tournament $T$ with vertex set $\{v_1, \dots, v_n\}$ such that $d_T^-(v_i) \le s_i$ for all $i \in [n]$ if and only if $\sum_{i=1}^k s_i \ge \binom{k}{2}$ for all $k \in [n]$.

*Proof.* Assume first that there is a tournament $T$ with vertex set $\{v_1, \dots, v_n\}$ such that $d_T^-(v_i) \le s_i$ for all $i \in [n]$. Then for every $k \in [n]$,

$$\binom{k}{2} = |A(T(\{v_1, \dots, v_k\}))| \le \sum_{i=1}^{k} d_T^-(v_i) \le \sum_{i=1}^{k} s_i.$$
Let us now prove the reciprocal by induction on $Exc = \sum_{i=1}^{n} s_i - \binom{n}{2}$.

If $Exc = 0$, then the results follows from Landau's Theorem. Assume now that $Exc > 0$. Let $r$ be the smallest integer such that $s_r = s_n$. Set $s'_r = s_r - 1$ and $s'_i = s_i$ for all $i \in [n] \setminus \{r\}$. We shall prove that $\sum_{i=1}^k s'_i \ge \binom{k}{2}$ for all $k \in [n]$. Thus, by the induction hypothesis, there is a tournament $T$ with vertex set $\{v_1, \dots, v_n\}$ such that $d_T^-(v_i) \le s'_i$ for all $i \in [n]$. Since $s'_i \le s_i$ for all $i \in [n]$, we get the result.

Therefore assume for a contradiction that there exists $k$ such that $\sum_{i=1}^k s'_i < \binom{k}{2}$. Choose such a $k$ that is minimum. Clearly $r \le k < n$ (in particular, $k < n$ because $Exc > 0$), so $s_k = s_n$. Moreover $s'_k = \sum_{i=1}^k s'_i - \sum_{i=1}^{k-1} s'_i < \binom{k}{2} - \binom{k-1}{2} = k$. So $s_k \le s'_k + 1 \le k$, and thus $s_i \le k$ for all $k \le i \le n$. Hence

$$ \sum_{i=1}^{n} s_i = \sum_{i=1}^{k} s_i + \sum_{i=k+1}^{n} s_i \le \sum_{i=1}^{k} s_i + k(n-k) \le \binom{k}{2} + k(n-k) < \binom{n}{2} $$

because $k < n$. This a contradiction and completes the proof. $\square$

**Corollary 5.6.** *Checking if a sequence is $k_1$-suitable can be done in polynomial time.*

*Proof.* Let $\vec{d} = (d_1, \dots, d_{k_2})$ be a sequence. Free to permute the indices, we may assume that the sequence is non-increasing. By Lemma 5.3, $\vec{d}$ is $\vec{d}$ is $k_1$-suitable if and only if there is a tournament $T$ with vertex set $\{v_1, \dots, v_{k_2}\}$ such that $d_T^-(v_i) \le k_1 - i - d_i$ for all $i \in [k_2]$. By Corollary 5.5, there is such a tournament if and only if $\sum_{i=1}^k k_1 - i - d_i \ge \binom{k}{2}$ for all $k \in [k_2]$. Each of this $k_2$ inequalities can easily be checked in linear time. $\square$

Now we are ready to complete the proof of Theorem 5.1.

*Proof of Theorem 5.1.* Let $G$ be a cobipartite graph with cobipartition $(K_1, K_2)$. Set $k_1 = |K_1|$. By Lemma 5.2, $\vec{\chi}_s(G) = k_1 - 1$ if and only if the following hold.

(i) There is an antimatching saturating $K_2$ in the bipartite graph induced by $E(K_1, K_2)$.

(ii) $(d_{K_1}(v_1), \dots, d_{K_1}(v_{k_2}))$ is a $k_1$-suitable sequence.

Checking if there is an antimatching saturating $K_2$ can be done in polynomial time using any matching algorithm in the complement.

Checking if a sequence is $k_1$-suitable can be done in polynomial time by Corollary 5.6. $\square$

Nevertheless, the following problems remain open.

**Problem 5.7.** For any fixed positive integer $\ell$, what is the complexity of deciding whether $\vec{\chi}_s(G) = |K_1|-1+\ell$ for a given cobipartite graph with cobipartition $(K_1, K_2)$?

**Problem 5.8.** What is the complexity of deciding whether $\vec{\chi}(G) = |K_1| - 1$ for a given cobipartite graph with cobipartition $(K_1, K_2)$?

**Problem 5.9.** Is it possible to characterize the cobipartite graphs $G$ with cobipartition $(K_1, K_2)$ such that $\vec{\chi}_s(G) \le |K_1| + |K_2| - 2$?

# 6 Parameterized Complexity

We now study the parameterized complexity of determining if the semi-proper orientation number of a graph $G$ is at most $k$ when parameterized by the size of a minimum vertex cover in $G$, neighbourhood diversity of $G$ plus $k$, treewidth of $G$, and only by the value of $k$. The result for neighbourhood diversity plus $k$, and the kernel for cographs also hold for the proper orientation number. Some results in this section use similar ideas to the ones presented in [4].
## 6.1 Vertex Cover

Given a graph $G = (V, E)$, a subset $S \subseteq V$ is a **vertex cover** of $G$ if, for every $uv \in E$, we have that $u \in S$ or $v \in S$. Then, define $\text{vc}(G) = \min\{|S| \mid S \text{ is a vertex cover of } G\}$. With these definitions, let us present the first parameterization.

**SEMI-PROPER ORIENTATION PARAMETERIZED BY VERTEX COVER**

**Input:** A graph $G$ and a positive integer $k$.

**Parameter:** $\text{vc}(G)$.

**Question:** Is $\vec{\chi}_s(G) \le k$?

Let us prove that SEMI-PROPER ORIENTATION PARAMETERIZED BY VERTEX COVER is FPT by showing that it admits an exponential kernel.

**Theorem 6.1.** SEMI-PROPER ORIENTATION PARAMETERIZED BY VERTEX COVER has a kernel of size $O(4^{\text{vc}(G)} \text{vc}(G)^2)$.

*Proof.* Let $(G, k)$ be an instance of SEMI-PROPER ORIENTATION PARAMETERIZED BY VERTEX COVER where $G$ is a connected graph. We construct, in polynomial time, an equivalent instance $(G', k)$ such that $|V(G')| = O(4^{\text{vc}(G)} \text{vc}(G)^2)$.

First, since $G$ admits a vertex cover of size $\text{vc}(G)$, then its vertex-set can be partitioned into two sets $A$ and $B$ such that $|A| = \text{vc}(G)$ and $B$ is an independent set. It follows that the degeneracy of $G$ satisfies $\delta^*(G) \le \text{vc}(G)$. Thus, we know that $\vec{\chi}_s(G) \le 2 \text{vc}(G)$ as it is always true that $\vec{\chi}_s(G) \le 2\delta^*(G)$ [14].

Therefore, if $k \ge 2 \text{vc}(G)$, by the previous argument, the answer to SEMI-PROPER ORIENTATION PARAMETERIZED BY VERTEX COVER is “YES” (and one can just output $G'$ as a trivial vertex). Hence, let us assume that $k < 2 \text{vc}(G)$.

By using the well-known 2-approximation algorithm for VERTEX COVER, one may obtain in polynomial time a subset $C \subseteq V(G)$ such that $C$ is a vertex cover of $G$ and $|C| = \gamma \le 2 \text{vc}(G)$. Thus, notice that $V(G)$ can be partitioned into $C$ and an independent set $S$.

We partition the vertices of $S$ into at most $2^\gamma - 1$ non-empty subsets $S_i$ of twins, for $i \in \{1, \dots, 2^\gamma - 1\}$ (i.e., two vertices are in a same part if and only if they are twins). Let $M = k\gamma$.

**Claim 6.1.1.** If there exists $i \in \{1, \dots, 2^\gamma - 1\}$ such that $|S_i| \ge M + 2$, then removing $(|S_i| - (M + 1))$ vertices from $S_i$ builds a smaller graph $G'$ such that $\vec{\chi}_s(G) \le k$ if, and only if, $\vec{\chi}_s(G') \le k$.

*Proof:* Since the problem is monotone under subgraphs [14], we just need to prove that if $\vec{\chi}_s(G') \le k$, then $\vec{\chi}_s(G) \le k$.

Let $S'_i$ be the $M + 1$ remaining vertices of $S_i$ in $G'$. Note that, if $(D', w')$ is a semi-proper $k$-orientation of $G'$ such that exactly $\ell$ edges with one end in $C$ and the other in $S'_i$ are oriented towards $C$, then:

$$k \ge \max_{v \in C} d_{D'}(v) \ge \frac{\sum_{v \in C} d_{D'}(v)}{\gamma} \ge \frac{\ell}{\gamma}.$$

Therefore, $\ell \le k\gamma = M \le 4 \text{vc}^2(G)$. So, for every $i \in \{1, \dots, 2^\gamma - 1\}$ and every semi-proper $k$-orientation, there are at most $M$ edges oriented from $S'_i$ to $C$. Since $|S'_i| = M + 1$, note that $S'_i$ has a sink $s$ in $D'$. In order to build a semi-proper $k$-orientation $(D, w)$ of $G$, it suffices to extend $(D', w')$ to $G$ by making all the $|S'_i| - (M + 1)$ removed vertices of $S'_i$ as sinks and having the same in-weight as $s$. ■

By applying Claim 6.1.1 to each feasible $S_i$, $i \in \{1, \dots, 2^\gamma - 1\}$, we build a graph $G'$ as required.

$$\text{Note that } |G'| \le \gamma + (2^\gamma - 1)(M + 1) = O(4^{\text{vc}(G)} \text{vc}(G)^2). \quad \square$$

The above result still leaves open the problem of existence of a polynomial kernel.

**Problem 6.2.** Does there exist a polynomial kernel to SEMI-PROPER ORIENTATION PARAMETERIZED BY VERTEX COVER?
## 6.2 Neighborhood Diversity

Let us move to our second parameterization, based on the concept of neighbourhood diversity. The **neighbourhood diversity** of a graph $G$, denoted by $nd(G)$, is the minimum $k$ such that $G$ can be partitioned into at most $k$ subsets of twin vertices [21]. It is well known that if $G$ has a vertex cover $S$ satisfying $|S| \le k$, then $G$ can be partitioned into at most $2^k + k$ subsets of twin vertices (similarly to the proof of Theorem 6.1).

In the sequel, we prove that deciding whether $\vec{\chi}_s(G) \le k$, resp., $\vec{\chi}(G) \le k$, is FPT parameterized by the neighbourhood diversity of $G$ plus $k$.

### SEMI-PROPER ORIENTATION PARAMETERIZED BY NEIGHBOURHOOD DIVERSITY PLUS SOLUTION VALUE

**Input:** A graph $G$ and a positive integer $k$.

**Parameter:** $nd(G) + k$.

**Question:** Is $\vec{\chi}_s(G) \le k$?

### PROPER ORIENTATION PARAMETERIZED BY NEIGHBOURHOOD DIVERSITY PLUS SOLUTION VALUE

**Input:** A graph $G$ and a positive integer $k$.

**Parameter:** $nd(G) + k$.

**Question:** Is $\vec{\chi}(G) \le k$?

Let us first present a technical lemma and then prove the main result on parameterization by neighborhood diversity plus Solution value.

**Lemma 6.3.** *Given a positive integer $k$, if $G$ is a graph such that $\vec{\chi}(G) \le k$ or $\vec{\chi}_s(G) \le k$ and there are $S_1, S_2 \subseteq V(G)$ such that $S_1 \cap S_2 = \emptyset$ and $uv \in E(G)$ for every $u \in S_1$ and $v \in S_2$, then $\min\{|S_1|, |S_2|\} \le 2k$.*

*Proof.* For purpose of contradiction, let us assume that $|S_1|, |S_2| > 2k$. In any optimal proper orientation $D$ (resp. semi-proper orientation $(D, w)$) of $G$, there are at least $\frac{|S_1| \cdot |S_2|}{2} > 2k^2$ arcs oriented towards $S_i$, for some $i \in \{S_i\}$, say $S_1$. Hence, one vertex of $S_1$ has (resp. weighted) in-degree at least $k+1$, a contradiction. □

**Theorem 6.4.** *SEMI-PROPER ORIENTATION PARAMETERIZED BY NEIGHBOURHOOD DIVERSITY PLUS SOLUTION VALUE and PROPER ORIENTATION PARAMETERIZED BY NEIGHBOURHOOD DIVERSITY PLUS SOLUTION VALUE have a kernel of size at most $nd(G)(2k^2 + 1)$.*

*Proof.* Let $(G, k)$ be an instance of SEMI-PROPER ORIENTATION PARAMETERIZED BY NEIGHBOURHOOD DIVERSITY PLUS SOLUTION VALUE. We may assume that $G$ is connected. Let $nd(G) = d$. In linear time, we can obtain a partition $\mathcal{P} = \{N_1, \dots, N_d\}$ such that each $N_i$ is composed by twin vertices, for each $i \in \{1, \dots, d\}$. Let $i \in \{1, \dots, d\}$. By definition, note that the subgraph of $G$ induced by $N_i$ is either a clique or an independent set. In the case when $G[N_i]$ is a complete subgraph, if $|N_i| \ge k+2$, the instance $(G, k)$ is trivially a “NO” instance and our kernelization algorithm just outputs the equivalent instance $(K_{k+2}, k)$.

Let us consider a set $N_i$ which induces a stable set. Since $G$ is connected, there must be a set $N_j$, $j \ne i$, such that there are all edges between the vertices of $N_i$ and the vertices of $N_j$. By Lemma 6.3, either $|N_i| \le 2k$ or $|N_j| \le 2k$. Let us consider the latter case. If $|N_i| > 2k^2 + 1$, let us build an equivalent instance $(G', k)$ by removing $|N_i| - (2k^2 + 1)$ vertices from $N_i$.

Let us show then that $\vec{\chi}(G) \le k$ if, and only if $\vec{\chi}(G') \le k$. Let $D$ be a proper $k$-orientation of $G$. If $|N_i| > 2k^2$, then at least $|N_i| - 2k^2$ vertices of $N_i$ must be sinks. Indeed, otherwise, at least $2k^2 + 1$ arcs are oriented from $N_i$ to $N_j$ and, since $|N_j| \le 2k$, at least one vertex of $N_j$ has in-degree at least $k+1$, a contradiction. Let $S \subseteq N_i$ be the set of sinks and let $v \in S$. Let $D' = D - (S \setminus \{v\})$. Then $D'$ is a proper $k$-orientation of $G'$. Reciprocally, let $D'$ be a proper $k$-orientation of $G'$. By the same reasoning (since $N_i$ has size $2k^2 + 1$ in $G'$), there exists at least one sink $v \in N_i$ in $D'$. Let us build $D$ by copying $D'$ and making the extra $|N_i| - (2k^2 + 1)$ vertices of $N_i$ as sinks. Then, $D$ is a proper $k$-orientation of $G$.

Repeating this process for all $N_i$, we build an equivalent instance $G'$ such that, for every $1 \le i \le d = nd(G)$, $|N_i| \le 2k^2 + 1$. Hence, $|V(G')| \le nd(G)(2k^2 + 1)$.
Note that $\vec{\chi}_s(G') \le \vec{\chi}_s(G)$ by Lemma 1.3. To prove that if $\vec{\chi}_s(G') \le k$ then, $\vec{\chi}_s(G) \le k$ one can use analogous arguments as in the previous case. $\square$

The above result shows that parameterizing SEMI-PROPER ORIENTATION by the neighborhood diversity plus the solution value not only leads to an FPT algorithm, but even yields a polynomial kernel. It leaves open the question whether adding the solution value is necessary for an FPT algorithm or a polynomial kernel.

**Problem 6.5.** Is SEMI-PROPER ORIENTATION an FPT problem when parameterized by the neighbourhood diversity?

## 6.3 Treewidth

Let us now present a parameterization based on the concept of tree-decomposition. Recall that a **tree-decomposition** of a graph $G = (V, E)$ is a pair $(T, \mathcal{X})$ where $T$ is a tree and $\mathcal{X} = \{X_v \mid v \in V(T)\}$ is a family of subsets of $V$ such that:

(a) $\bigcup_{v \in V(T)} X_v = V$;

(b) for every $e = uw \in E$, there exists $v \in V(T)$ with $u, w \in X_v$;

(c) for every $u \in V$, $\{v \in V(T) \mid u \in X_v\}$ induces a subtree of $T$.

The **width** $w(D)$ of $D = (T, \mathcal{X})$ equals $\max_{v \in V(T)} |X_v| - 1$, and the **treewidth** of $G$, denoted by $\mathrm{tw}(G)$, is the minimum width of its tree-decompositions.

A tree-decomposition $(T, \mathcal{X})$ of $G$ of width $t$ is **nice** if $T$ is a rooted tree with maximum degree 3, the root has at most two children and every node $v \in V(T)$ satisfies one of the following:

**Leaf node:** $v$ is a leaf (and not the root) and $|X_v| = t + 1$;

**Forget node:** $v$ has one child $v'$ and, there exists $u \in V$ such that $X_v = X_{v'} \setminus \{u\}$;

**Introduce node:** $v$ has one child $v'$ and, there exists $u \in V$ such that $X_v = X_{v'} \cup \{u\}$;

**Join node:** $v$ has two children $v'$ and $v''$ and $X_v = X_{v'} = X_{v''}$.

It is well known that, for any graph $G$ on $n$ vertices, a nice tree-decomposition $D = (T, \mathcal{X})$ of $G$ with $\mathrm{tw}(G) \le w(D) \le t$ such that $|V(T)| = \mathcal{O}(n)$ can be computed in linear time from any tree-decomposition with width at most $t$ of $G$ [8]. In the sequel, we prove that the following problem is FPT:

SEMI-PROPER ORIENTATION PARAMETERIZED BY TREEWIDTH

Input: A graph $G$ and a positive integer $k$.

Parameter: $\mathrm{tw}(G)$.

Question: Is $\vec{\chi}_s(G) \le k$?

Let $G = (V, E)$ be a graph, $F \subseteq E$ and let $w': F \to \{1, 2\}$ and $\vec{F}$ be an orientation of the edges in $F$. A weighted orientation $(\vec{G}, w: E \to \{1, 2\})$ of $G$ ** extends** $(w', \vec{F})$ if $w \upharpoonright_F = w'$ and $\vec{F}$ **agrees** with $\vec{G}$ on $F$, i.e. if $uv \in F$, then $(u, v) \in A(\vec{G})$ if, and only if, $(u, v) \in \vec{F}$.

**Theorem 6.6.** Let $t \ge 1$. For any $k \ge 0$ and any graph $G$ on $n$ vertices with treewidth at most $t$, deciding whether $\vec{\chi}_s(G) \le k$ can be computed in $4^{O(t^2)}$ time.

*Proof.* Let $k \ge 0$ and $G$ be any graph on $n$ vertices with treewidth at most $t$. Because $\vec{\chi}_s(G) \le 2\delta^*(G)$ [14] and $\delta^*(G) \le \mathrm{tw}(G) \le t$, if $k \ge 2t$, then $\vec{\chi}_s(G) \le k$. Hence, we may assume that $k < 2t$.
First, a nice tree-decomposition $(T, \mathcal{X})$ with $O(n)$ nodes and of width at most $2t$ of $G$ can be computed in $2^{O(t)}n$ time [20]. Let $r \in V(T)$ be the root of $T$. For every $v \in V(T)$, let $T_v$ be the subtree of $T$ rooted in $v$ and let $G_v$ be the subgraph of $G$ induced by $\bigcup_{h \in V(T_v)} X_h$.

Let us design a bottom-up dynamic programming algorithm that computes, for every $v \in V(T)$, the set $O_v$ of all the triples $(L, C, O')$ where $L: X_v \to 2^{\{0, \dots, k\}}$, $C: X_v \to \{0, \dots, k\}$ and $O'$ is a weighted orientation of $G[X_v]$ such that there exists a weighted orientation $O = (D, w)$ of $G_v$ satisfying:

* $S_{(D,w)} \le k$;

* $O$ extends $O'$; and

* for every vertex $u \in X_v$, $S_{D,w}(u) = C(u)$ and $L(u) = \{0, \dots, k\} \setminus \{S_{D,w}(x) \mid x \in N_{G_v}(u) \setminus X_v\}$.

Intuitively, $C(u)$ represents the current colour of $u$ in the weighted orientation $O$ that extends $O'$ and $L(u)$ corresponds to the set of available colours that $u$ may use later (the ones that are not the colours of the neighbours of $u$ in $V(G_v) \setminus X_v$).

For every leaf $\ell \in V(T)$, let $SO_\ell = \{(D, w) \mid (D, w)$ is semi-proper $k$-orientation of $G_\ell)\}$. For every $v \in X_\ell$ and $(D, w) \in SO_\ell$, define $C_{(D,w)}(v) = S_{(D,w)}(v)$ and $L(v) = \{0, \dots, k\}$. Thus, define $O_\ell = \{(L, C_{(D,w)}, O') \mid O' = (D, w) \in SO_\ell\}$. Note that $|X_\ell| = O(t)$, so $|E(G_\ell)| = O(t^2)$ and, since each edge can take two values [14] and two orientations, $|SO_\ell| \le 4^{O(t^2)}$, and so $|O_\ell| \le 4^{O(t^2)}$.

Now, let $v \in V(T)$ be a non-leaf node and assume that $O_v'$ has been computed for every child $v'$ of $v$. We explain how to compute $O_v$ from the set(s) of its child(ren). There are three cases to be considered depending on the type of $v$.

**Forget node:** Let $v'$ be the unique child of $v$ and let $X_v = X_{v'} \setminus \{u\}$. The set $O_v$ is obtained as follows. For every $(L', C', O') \in O_{v'}$, let $O$ be the weighted orientation of $G[X_v]$ such that $O'$ extends $O$ to $G[X_{v'}]$. For every $x \in X_v \cap N(u)$, let $L(x) = L'(x) \setminus \{C'(u)\}$. Then, add $(L, C'_{|X_v}, O)$ to $O_v$, where $C'_{|X_v}$ is the restriction of $C$ to $X_v$.

**Join node:** Let $v'$ and $v''$ be the two children of $v$. The set $O_v$ is obtained as follows. For every $(L', C', O') \in O_{v'}$ and $(L'', C'', O'') \in O_{v'}$ such that $O' = O''$, let $O = O' = (D, w)$ and $C = C'$. Moreover, for every $x \in X_v$, let $C(x) = C'(x) + C''(x) - \sum_{u \in X_v, ux \in A(D)} w(ux)$ and let $L(x) = L'(x) \cap L''(x)$. If, for all $u, x \in X_v$, $C(x) \in L(x)$ and, if $ux \in A(D)$ or $xu \in A(D)$, then $C(x) \neq C(u)$, then add $(L, C, O)$ to $O_v$.

**Introduced node:** Let $v'$ be the unique child of $v$ and let $X_v = X_{v'} \cup \{u\}$. The set $O_v$ is obtained as follows. For every $(L', C', O') \in O_{v'}$ and for every weighted orientation $O = (D, w)$ of $X_v$ that extends $O'$, let $C(u) = S_{(D,w)}(u)$ and let $L(u) = \{0, \dots, k\}$. Then, for every $x \in X_v \setminus \{u\}$, let $C(x) = C'(x) + w(ux)$ if $ux \in A(D)$ and let $C(x) = C'(x)$ otherwise; and let $L(x) = L'(x)$. If, for all $u, x \in X_v$, $C(x) \in L(x)$ and, if $ux \in A(D)$ or $xu \in A(D)$, then $C(v) \neq C(u)$, then add $(L, C, O)$ to $O_v$.

Clearly, $\vec{\chi}_s(G) \le k$ if and only if $O_r \neq \emptyset$, where $r$ is the root of $T$. Moreover, the number of orientations to be considered at any node $v \in V(T)$ is at most $4^{O(t^2)}$ and, for each vertex of $X_v$, the number of possible values of the function $L$ is $O(2^k) = O(4^t)$ since $k \le 2t$ and the number of possible values of the function $C$ is $k+1 = O(t)$. This implies that $|O_v| = 4^{O(t^2)} \cdot O(t^k) \cdot (4^t)^t$, which gives the desired time complexity. $\square$

## 6.4 Natural parameter

In this section, we combine the results of Sections 6.1, 6.2 and 6.3 to obtain results with parameterization by the value of the solution. Some ideas are similar to the ones presented in [4].

### PARAMETERIZED PROPER ORIENTATION

**Input:** A graph $G$ and a positive integer $k$.

**Parameter:** $k$.

**Question:** Is $\vec{\chi}(G) \le k$?
PARAMETERIZED SEMI-PROPER ORIENTATION

Input: A graph $G$ and a positive integer $k$.

Parameter: $k$.

Question: Is $\vec{\chi}_s(G) \le k$?

It is important to recall that **PARAMETERIZED SEMI-PROPER ORIENTATION** is para-NP-complete in the class of planar bipartite graphs [14].

In the sequel, we argue that a kernel of size polynomial in $k$ is unlikely to exist even for the class of chordal graphs. For this, we need the following definition and result.

**Definition 6.7 (AND-cross-composition).** Let $L \subseteq \Sigma^*$ be a language and $Q \subseteq \Sigma^* \times \mathbb{N}$ be a parameterized language. We say that $L$ **AND-cross-composes** into $Q$ if there exists a polynomial equivalence relation $\mathcal{R}$ and an algorithm $\mathcal{A}$, called a **cross-composition**, satisfying the following conditions. The algorithm $\mathcal{A}$ takes as input a sequence of strings $x_1, x_2, \dots, x_t \in \Sigma^*$ that are equivalent with respect to $\mathcal{R}$, runs in time polynomial in $\sum_{i=1}^t |x_i|$, and outputs one instance $(y, k) \in \Sigma^* \times \mathbb{N}$ such that:

1. $k \le p(\max_{i=1}^t |x_i| + \log t)$ for some polynomial function $p(\cdot)$, and

2. $(y, k) \in Q$ if and only if $x_i \in L$, for every $i \in \{1, \dots, t\}$.

**Theorem 6.8 (Drucker [15], see also [16]).** *Assume that an NP-hard language $L$ AND-cross-composes into a parameterized language $Q$. Then $Q$ does not admit a polynomial compression, unless $\mathrm{NP} \subseteq \mathrm{coNP}/\mathrm{poly}$.*

Now, given graphs $G_1, \dots, G_p$ with disjoint vertex sets, for some $p \ge 2$, the **disjoint union**, or simply **union**, of $G_1, \dots, G_p$ is the graph $G_1 \cup \dots \cup G_p$ such that $V(G_1 \cup \dots \cup G_p) = V(G_1) \cup \dots \cup V(G_p)$ and $E(G_1 \cup \dots \cup G_p) = E(G_1) \cup \dots \cup E(G_p)$.

Let us present the following series of results on chordal and split graphs.

**Proposition 6.9.** If $G = G_1 \cup \dots \cup G_p$, then $\vec{\chi}_s(G) = \max\{\vec{\chi}_s(G_1), \dots, \vec{\chi}_s(G_p)\}$, for any $p \ge 2$.

**Proposition 6.10.** **PARAMETERIZED SEMI-PROPER ORIENTATION** does not admit polynomial kernel for chordal graphs, unless $\mathrm{NP} \subseteq \mathrm{coNP}/\mathrm{poly}$.

*Proof.* By just taking the disjoint union of $t$ instances of **SEMI-PROPER ORIENTATION** in split graphs with the same $k$ (this is the equivalence relation $\mathcal{R}$), we have an AND-cross-composition to an instance of **PARAMETERIZED SEMI-PROPER ORIENTATION** in chordal graphs as the disjoint union of split graphs is chordal and Proposition 6.9 holds. Thus, it follows, by Theorem 6.8. □

**Proposition 6.11.** **PARAMETERIZED SEMI-PROPER ORIENTATION** can be solved in $4^{O(k^2)} \cdot n$ time for chordal graphs.

*Proof.* The algorithm presented Theorem 6.6 decides whether $\vec{\chi}_s(G) \le k$, when $G$ has treewidth at most $t$, in $4^{O(t^2)} \cdot n$ time. Thus, given a chordal graph $G$, one may compute $\omega(G)$ in polynomial time, as they are perfect. In case $\omega(G) \ge k+2$, then the answer to **PARAMETERIZED SEMI-PROPER ORIENTATION** is trivially “NO”. Otherwise, note that a chordal graph with $\omega(G) \le k+1$ is a graph with treewidth at most $k$. Then, the result follows by Theorem 6.6. □

**Proposition 6.12.** **PARAMETERIZED SEMI-PROPER ORIENTATION** admits a $O(2^k k^2)$-kernel for split graphs.

*Proof.* Let $\{K, S\}$ be a partition of $V(G)$ such that $K$ is a maximum clique of $G$ and $S$ is a stable set. Recall that $|K|$ can be computed in linear time as $G$ is chordal. By Proposition 6.9, we can suppose that $G$ is connected.

Note that if $|K| \ge k+2$ the answer is trivially “NO” and one can output a trivial equivalent instance as $K_{k+2}$. Otherwise, note that $K$ is a vertex cover of $G$ and thus $\mathrm{vc}(G) \le |K| \le k+1$. Consequently, one may just apply the algorithm in Theorem 6.1. Note that, contrary to the algorithm in 6.1, here we directly get a vertex cover $K$ of size at most $k+1$ (not at most $2k$ as in Theorem 6.1 that uses a 2-approximation algorithm for **VERTEX COVER**. Therefore, the size of the kernel is slightly improved to $O(2^k k^2)$ in this case. □
In view of the above results, it is natural to ask the following.

**Problem 6.13.** Does there exist a polynomial kernel to PARAMETERIZED SEMI-PROPER ORIENTATION in split graphs?

Let us now address another dense-graph class admitting an exponential kernel for the natural parameter. Given $p \ge 2$ graphs $G_1, \dots, G_p$ with disjoint vertex sets, the **join** $G_1 + \dots + G_p$ of these graphs be the graph obtained from the disjoint union of $G_1, \dots, G_p$ by adding an edge $\{x, y\}$ for every $x \in V(G_i)$ and $y \in V(G_j)$, for every $1 \le i < j \le p$. The class of **cographs** is defined recursively as follows:

* a trivial graph (with one vertex and no edge) is a cograph;

* the join of cographs is a cograph, and

* the disjoint union of cographs is a cograph.

Any cograph $G$ admits a unique **cotree** $T(G)$ defined recursively as follows. If $G$ has a unique vertex, then its cotree $T(G)$ is the rooted tree with a single node mapped to the single vertex of $V(G)$. If $G$ is the disjoint union of connected cographs $G_1, \dots, G_p$, then, the cotree $T$ of $G$ is obtained from $T(G_1), \dots, T(G_p)$ by adding a root $v$ (called a **union node**) linked to the roots of each $T(G_i)$, $1 \le i \le p$. If $G$ is the join of not connected and/or single vertex cographs $G_1, \dots, G_p$, then, the cotree $T$ of $G$ is obtained from $T(G_1), \dots, T(G_p)$ by adding a root $v$ (called a **join node**) linked to the roots of each $T(G_i)$, $1 \le i \le p$. Note that the join nodes and union nodes of $T(G)$ define a bipartition of the internal vertices of $T(G)$. Note also that there is a one-to-one mapping between the leaves of $T(G)$ and $V(G)$. This implies the following:

**Proposition 6.14.** Let $G$ be a cograph with cotree $T(G)$ and $k \in \mathbb{N}$. If there exists $f: \mathbb{N} \to \mathbb{N}$ such that $T(G)$ has depth at most $f(k)$ and maximum degree $f(k)$, then $|V(G)| \le f(k)^{f(k)}$.

As one may expect at this point, our kernelization algorithm uses the cotree $T$ of a given cograph $G$ to build an equivalent instance of bounded size. In the next lemmas, we show how to bound the depth and the degree of $T$ as well as the number of vertices in $G(v_i)$ for every child $v_i$ of an inner node $v$ of $T$.

For every $t \in V(T(G))$, let $G_t$ be the cograph whose cotree is $T_t$, which is the subtree of $T(G)$ rooted in $t$. Note that $V(G_t)$ is a **module** of $G$, i.e., for every $u \in V(G) \setminus V(G_t)$ either $\{u, w\} \in E(G)$ for all $w \in V(G_t)$ or $\{u, w\} \notin E(G)$ for all $w \in V(G_t)$. Given a rooted tree $T$ with root $r \in V(T)$, the **depth** of $T$ is the maximum length of a $r$, $v$-path in $T$, for some (leaf) $v \in V(T)$.

**Lemma 6.15.** Let $G$ be a connected cograph and $k$ be a positive integer. If $\vec{\chi}(G) \le k$ or $\vec{\chi}_s(G) \le k$, then the depth of $T(G)$ is at most $2k + 2$.

*Proof.* Let $P = (r = t_0, t_1, \dots, t_\ell)$ be a path from the root $r$ of $T(G)$ to a leaf $t_\ell$ with length $\ell$. Note that, since $r$ is a join node (because $G$ is connected), $t_{2i}$ is a join node for every integer $i \ge 0$.

Thus, for every, $0 \le i < \ell/2$, let $t'_i \ne t_{2i+1}$ be a child of $t_{2i}$ in $T(G)$ not in $P$ and let $v_i \in G(t'_i)$. Then $G[\{v_0, \dots, v_{\ell/2-1}\}]$ induces a complete subgraph of $G$ with $\ell/2$ vertices. If $\ell > 2k + 2$, then $\ell/2 - 1 > k$, which implies that $\vec{\chi}(G) \ge \vec{\chi}_s(G) \ge \omega(G) - 1 \ge \ell/2 - 1 > k$, a contradiction. $\square$

**Lemma 6.16.** Let $G$ be a cograph with $\vec{\chi}(G) \le k$ or $\vec{\chi}_s(G) \le k$ for some positive integer $k$. Then, for every join node $t \in V(T(G))$, $t$ has at most $k+1$ children and at most one child $t'$ of $t$ is such that $|V(G_{t'})| > 2k$.

*Proof.* If there is a join node $t \in V(T(G))$ with at least $k+2$ children, by the definition of the join operation, we deduce that $\omega(G) \ge k + 2$. This would contradict the fact that $\vec{\chi}(G) \le k$ or $\vec{\chi}_s(G) \le k$. If $t \in V(T(G))$ has at least two children $t'$ and $t''$ such that $|V(G_{t'})| > 2k$ and $|V(G_{t''})| > 2k$, then $\vec{\chi}_s(G) > k$ and $\vec{\chi}(G) > k$ by Lemma 6.3, a contradiction. $\square$
Let $k \in \mathbb{N}$. A cograph $G$ is $k$-nice if the depth of $T(G)$ is at most $2k+2$ and every join node $t \in V(T(G))$ has at most $k+1$ children, and at most one child $t'$ of $t$ is such that $|V(G_{t'})| > 2k$. For every integer $j \ge 0$, a node $t \in V(T(G))$ is called $j$-high if the depth of $T_t$ equals $j$.

For every $0 \le j \le 2k+1$, let $f_j : \mathbb{N} \to \mathbb{N}$ be recursively defined as follows. First, $f_0(x) = 1$ for every $x \in \mathbb{N}$. Then, for every $0 < j \le 2k+1$ and $x \in \mathbb{N}$, let $g_j(x)$ be the number of connected cographs with $f_j(x)$ vertices and $f_j(x) = (2x^2+1)g_{j-1}(x)f_{j-1}(x)$.

The cotree $T(G)$ is $(j,k)$-thin if, for every $0 \le j' \le j$, and for every $j'$-high node $t \in V(T(G))$, we have that $|V(G_t)| \le f_{j'}(k)$. Note that, if $T(G)$ has depth at most $d \le 2k+2$ and it is $(d,k)$-thin, then $|V(G)| \le f_d(k)$, i.e., the number of vertices of $G$ is a function only on $k$.

**Theorem 6.17.** *PARAMETERIZED SEMI-PROPER ORIENTATION and PARAMETERIZED PROPER ORIENTATION* *admit a kernel of size* $f_{2k+3}(k)$ *in cographs*.

*Proof.* Let $k \in \mathbb{N}$. First let us consider a connected cograph $G = (V, E)$ with cotree $T(G)$. If $G$ is not $k$-nice, then $\overrightarrow{\chi}(G) > k$ and $\overrightarrow{\chi_s}(G) > k$ by Lemmas 6.15 and 6.16, and so we may return a trivial kernel (e.g., a clique of size $k+2$). Hence, we may assume that $G$ is $k$-nice.

**Claim 6.17.1.** *For every $j \in \{0, \dots, 2k+1\}$, there exists a $k$-nice connected cograph $G'$ with $T(G')$ being $(j,k)$-thin such that $\overrightarrow{\chi}(G) \le k$ (resp., $\overrightarrow{\chi_s}(G) \le k$) if and only if $\overrightarrow{\chi}(G') \le k$ (resp., $\overrightarrow{\chi_s}(G') \le k$).*

*Proof of Claim.* We prove the claim by induction on $j$.

Note that the leaves of $T(G)$ correspond to vertices of $G$ and so $T(G)$ is $(0,k)$-thin, and so the induction hypothesis holds for $j=0$.

Let $0 \le j \le 2k+2$ and let us assume by induction that there exists a $k$-nice connected cograph $G'$ such that $T(G')$ is $(j,k)$-thin and $\overrightarrow{\chi}(G) \le k$ (resp., $\overrightarrow{\chi_s}(G) \le k$) if and only if $\overrightarrow{\chi}(G') \le k$ (resp., $\overrightarrow{\chi_s}(G') \le k$). If $j=2k+2$, we are done since $T(G)$ has depth at most $2k+2$ because $G$ is $k$-nice. Otherwise, let us show that the induction hypothesis also holds for $j+1$.

Let $t \in V(T(G'))$ be a $(j+1)$-high join node of $T(G')$. Then, because $G'$ is $k$-nice, $t$ has at most $k+1$ children, and for every child $t'$ of $t$ but one $t''$, $|V(G_{t'})| \le 2k$ and $|V(G_{t''})| \le f_j(k)$ by the induction hypothesis. Hence, $|V(G_t)| \le \max\{2(k+1)k, 2k^2 + f_j(k)\} \le f_{j+1}(k)$.

Let $t \in V(T(G'))$ be a $(j+1)$-high union node of $T(G')$. If $|V(G_t)| \le 2k \le f_{j+1}(k)$, we are done. Otherwise, let $X = N_G(V(G_t))$ (recall that $G_t$ is a module and so, we have all edges between $X$ and $V(G_t)$). Hence, by Lemma 6.3, $|X| \le 2k$. Let $t'_1, \dots, t'_p$ be the children of $t$ in $T(G')$. By induction, $|V(G_{t'_i})| \le f_j(k)$ for every $1 \le i \le p$.

Let $G''$ be the graph obtained from $G$ by keeping at most $2k^2+1$ copies of each subgraph $G_{t'_j}$, for $1 \le i \le p$. That is, if there exist $I \subseteq \{1, \dots, p\}$ such that $|I| > 2k^2+1$ and all subgraphs $G_{t'_j}$ are isomorphic, for every $j \in I$, then remove $|I| - (2k^2+1)$ children $t'_j$, $j \in I$, of $t$ in $T(G')$. Note that, after this operation, $t$ has at most $(2k^2+1)g_j(k)$ children, where $g_j(k)$ is the number of connected cographs with at most $f_j(k)$ vertices, and so $|V(G''_t)| \le (2k^2+1)g_j(k)f_j(k)$.

Clearly, $\overrightarrow{\chi_s}(G'') \le \overrightarrow{\chi_s}(G')$ since $\overrightarrow{\chi_s}$ is closed under taking subgraphs. To show that, if $\overrightarrow{\chi}(G') \le k$ then $\overrightarrow{\chi}(G'') \le k$, let $D'$ be a proper $k$-orientation of $G'$. For every $I \subseteq \{1, \dots, p\}$ such that $|I| > 2k^2+1$ and all subgraphs $G_{t'_j}$ are isomorphic to some graph $H$, for every $j \in I$, there must be at least $|I| - (2k^2+1)$ copies $C$ of $H$ such that, in $D'$, all edges are oriented from $X$ to $C$ (otherwise, at least one vertex of $X$ would have in-degree at least $k+1$ since $|X| \le 2k$). Let $D''$ be the orientation of $G''$ obtained from $D'$ by removing precisely these copies of $H$. Therefore, for every vertex of $G''$, its in-degree in $D''$ is the same as its in-degree in $D'$. Hence, $\overrightarrow{\chi}(G'') \le k$.

On the other hand, consider any proper $k$-orientation $D''$ of $G''$. For every subgraph $H$ isomorphic to some $V(G''_{t'})$ with $t'$ a child of $t$, there must be one copy of $H$ where all arcs are oriented from $X$ to $H$ (otherwise there would be at least $2k^2+1$ arcs to $X$ and one vertex of $X$ would have in-degree larger than $k$ as $|X| \le 2k$). Consider the orientation $D'$ of $G'$ obtained from $D''$ and by orienting all arcs from $X$ toward the extra copies of $H$ (and orienting the edges in the copies of $H$ as they are oriented in $H$). This implies that $\overrightarrow{\chi}(G) \le k$. Since $\overrightarrow{\chi_s}(G) \le \overrightarrow{\chi}(G)$, we also get that $\overrightarrow{\chi_s}(G) \le k$.

After having considered all $(j+1)$-high vertices, the induction hypothesis holds for $j+1$.

◇
Finally, we have to consider a disconnected cograph $G$, i.e., when we have a disjoint union of connected cographs $G_1, \dots, G_p$ at the root of $T(G)$. Note that $\vec{\chi}(G) = \max_{1 \le i \le p} \vec{\chi}(G_i)$ (resp., $\vec{\chi}_s(G) = \max_{1 \le i \le p} \vec{\chi}_s(G_i)$). By Claim 6.17.1, for every $1 \le i \le p$, we may find an instance $G'_i$ equivalent to $G_i$ and with order at most $f_{2k+2}(k)$. If $p$ is larger than the number $g_{2k+2}(k)$ of connected graphs with at most $f_{2k+2}(k)$ vertices, then two $G'_i$ and $G'_j$, $i \ne j$, must be isomorphic and we can remove one. Overall, we get a kernel of order at most $g_{2k+2}(k)f_{2k+2}(k) \le f_{2k+3}(k)$. $\square$

Although we present this exponential kernel for PARAMETERIZED PROPER ORIENTATION, the computational complexity for cographs remains open. This is an open problem posed by [4]. We have the same situation for the semi-proper orientation number:

**Problem 6.18.** What is the computational complexity of deciding whether $\vec{\chi}_s(G) \le k$ for a cograph $G$ and an integer $k$ given as inputs?

# 7 Further Research

Our NP-hardness proof computing $\vec{\chi}_s$ restricted to split graphs also implies NP-hardness for chordal graphs, but what is the complexity of computing $\vec{\chi}_s(G)$ when $G$ is an interval graph? In [4], the authors present an NP-hardness proof for computing $\vec{\chi}$ of chordal graphs, but the complexity for split graphs is open.

We have also shown that chordal graphs $G$ may have split subgraphs whose proper orientation number is at least $2\vec{\chi}(G) - 2$. Can the same happen with respect to (unit) interval graphs?

It seems a challenging question to determine the computational complexity of computing both $\vec{\chi}_s(G)$ and $\vec{\chi}(G)$ when $G$ is cobipartite or when $G$ is a cograph.

With respect to a split graph $G$, we have shown that computing $\vec{\chi}_s(G)$ is NP-hard, but there is an exponential kernelization algorithm when parameterized by the value of the solution. The straightforward question is whether this kernelization can be improved.

The authors in [4] presented a straightforward linear kernel for deciding $\vec{\chi}(G) \le k$ when $G$ is a cobipartite graph parameterized by $k$, as both cliques must have at most $k+2$ vertices. The same happens for $\vec{\chi}_s$. Actually, all parameterized complexity results for both $\vec{\chi}$ and $\vec{\chi}_s$ are so far “the same”, there is usually just a factor 2 that appears in the case of $\vec{\chi}_s$ due to optimal weighted orientations have weights in $\{1, 2\}$. A natural question is to find a graph class and a parameter in which the parameterized complexity of these problems differ.

# References

[1] AHADI, A., AND DEHGHAN, A. The complexity of the proper orientation number. Inform. Process. Lett. 113, 19-21 (2013), 799-803.

[2] AHADI, A., DEHGHAN, A., AND SAGHAFIAN, M. Is there any polynomial upper bound for the universal labeling of graphs? J. Comb. Optim. 34, 3 (2017), 760-770.

[3] AI, J., GERKE, S., GUTIN, G., SHI, Y., AND TAOQIU, Z. Proper orientation number of triangle-free bridgeless outerplanar graphs. Journal of Graph Theory 95, 2 (2020), 256-266.

[4] ARAUJO, J., CEZAR, A., LIMA, C., DOS SANTOS, V., AND SILVA, A. On the proper orientation number of chordal graphs. Theoretical Computer Science 888 (2021), 117-132.

[5] ARAUJO, J., COHEN, N., DE REZENDE, S. F., HAVET, F., AND MOURA, P. F. S. On the proper orientation number of bipartite graphs. Theoret. Comput. Sci. 566 (2015), 59-75.

[6] ARAUJO, J., HAVET, F., LINHARES SALES, C., AND SILVA, A. Proper orientation of cacti. Theoret. Comput. Sci. 639 (2016), 14-25.
[7] ARAUJO, J., SALES, C. L., SAU, I., AND SILVA, A. Weighted proper orientations of trees and graphs of bounded treewidth. *Theoretical Computer Science* 771 (2019), 39–48.

[8] BODLAENDER, H. L. A partial *k*-arboretum of graphs with bounded treewidth. *Theor. Comput. Sci.* 209, 1-2 (1998), 1–45.

[9] BONDY, A., AND MURTY, U. *Graph Theory*. Graduate Texts in Mathematics. Springer London, 2011.

[10] BOROWIECKI, M., GRYTCZUK, J., AND PILŚNIAK, M. Coloring chip configurations on graphs and digraphs. *Inform. Process. Lett.* 112, 1-2 (2012), 1–4.

[11] CHEN, Y., MOHAR, B., AND WU, H. Proper orientations and proper chromatic number. *Journal of Combinatorial Theory, Series B* 161 (2023), 63–85.

[12] CYGAN, M., FOMIN, F. V., KOWALIK, L., LOKSHTANOV, D., MARX, D., PILIPCZUK, M., PILIPCZUK, M., AND SAURABH, S. *Parameterized Algorithms*, 1st ed. Springer Publishing Company, Incorporated, 2015.

[13] DEHGHAN, A. On the in-out-proper orientations of graphs. *Discrete Applied Mathematics* 302 (2021), 129–138.

[14] DEHGHAN, A., AND HAVET, F. On the semi-proper orientations of graphs. *Discrete Applied Mathematics* 296 (2021), 9–25. 16th Cologne–Twente Workshop on Graphs and Combinatorial Optimization (CTW 2018).

[15] DRUCKER, A. New limits to classical and quantum instance compression. In *53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012* (2012), IEEE Computer Society, pp. 609–618.

[16] FOMIN, F. V., LOKSHTANOV, D., SAURABH, S., AND ZEHAVI, M. *Kernelization: Theory of Parameterized Preprocessing*. Cambridge University Press, 2019.

[17] HABIB, M., MCCONNELL, R. M., PAUL, C., AND VIENNOT, L. Lex-bfs and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. *Theor. Comput. Sci.* 234, 1-2 (2000), 59–84.

[18] KARP, R. Reducibility among combinatorial problems. In *Complexity of Computer Computations*, R. Miller and J. Thatcher, Eds. Plenum Press, 1972, pp. 85–103.

[19] KNOX, F., MATSUMOTO, N., HERMOSILLO DE LA MAZA, S. G., MOHAR, B., AND LINHARES SALES, C. Proper orientations of planar bipartite graphs. *Graphs Combin.* 33, 5 (2017), 1189–1194.

[20] KORHONEN, T. A single-exponential time 2-approximation algorithm for treewidth. In *62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022* (2021), IEEE, pp. 184–192.

[21] LAMPIS, M. Algorithmic meta-theorems for restrictions of treewidth. *Algorithmica* 64, 1 (Sep 2012), 19–37.

[22] LANDAU, H. G. On dominance relations and the structure of animal societies: III the condition for a score structure. *The Bulletin of Mathematical Biophysics* 15, 2 (Jun 1953), 143–148.