Given an integer k ⩾ 1, a digraph D is k-arc-strong if the removal of any set of at most k-1 arcs of D yields a strongly connected digraph. For a digraph D and some set X ⊆ V(D), the inversion of X is the operation of flipping all arcs both of whose endvertices are in X. We initiate the study of establishing arc-connectivity properties by applying inversions of bounded or fixed size. For fixed-size inversions, we consider the feasibility of the problem by characterizing, for all integers p ⩾ 2 and k ⩾ 1, the digraphs that can be made k-arc-strong by applying inversions of size exactly p, provided a minimum size of the digraphs. For bounded-size inversions, the tractability of the feasibility problem follows easily from a famous theorem of Nash-Williams, so we focus on minimising the number of inversions. We prove that for all integers p ⩾ 3 and k ⩾ 1 and any ε > 0, there exists a polynomial-time (4k-2+ε)-approximation algorithm for computing the minimum number of inversions of size at most p that make a given digraph k-arc-strong. This is in stark contrast to other results on inversion optimization problems. On the other hand, we show that for any p ⩾ 3 and k ⩾ 1 the problem is NP-hard, and, moreover, APX-hard. As a result on parameterized complexity, we show that for any k ⩾ 2, it is W[1]-hard with respect to p to decide whether a given digraph can be made k-arc-strong by applying a single inversion of size at most p. We also prove that for a given multidigraph, it is W[1]-hard with respect to 𝓁 to decide whether it can be made 2-arc-strong by applying 𝓁 inversions of size 2.

A proper k -colouring of a graph G = (V, E) is a function c : V(G) → {1,..., k} such that c(u) ≠ c(v) for every edge uv ∈ E(G). The chromatic number χ(G) is the minimum k such that there exists a proper k -colouring of G. Given a spanning subgraph H of G , a q-backbone k -colouring of (G,H) is a proper k -colouring c of G such that | c(u) - c(v) | ≥ q for every edge uv ∈ E(H). The q -backbone chromatic number BBC q (G, H) is the smallest k for which there exists a q -backbone k-colouring of (G,H). In their seminal paper, Broersma et al. [12] ask whether, for any chordal graph G and any spanning forest H of G , we have that BBC 2 ( G, H) ≤ χ( G ) + O( 1) . In this work, we first show that this is true as long as H is bipartite and G is an interval graph in which each vertex belongs to at most two maximal cliques. We then show that this does not extend to bipartite graphs as backbone by exhibiting a family of chordal graphs G with spanning bipartite subgraphs H satisfying BBC 2 (G,H)≥5χ(G)/3. Then, we show that if G is chordal and H has bounded maximum average degree (in particular, if H is a forest), then BBC 2 (G,H)≤χ(G) + O(√χ(G)). We finally show that BBC 2 (G,H) ≤ 3/2χ(G) + O(1) holds whenever G is chordal and H is C 4 -free.

Reed in 1998 conjectured that every graph G satisfies . As a partial result, he proved the existence of ε > 0 for which every graph G satisfies . We propose an analogue conjecture for digraphs. Given a digraph D, we denote by (D ) the dichromatic number of D, which is the minimum number of colours needed to partition D into acyclic induced subdigraphs. We let denote the size of a largest biclique (a set of vertices inducing a complete digraph) of D and . We conjecture that every digraph D satisfies , which if true implies Reed’s conjecture. As a partial result, we prove the existence of ε > 0 for which every digraph D satisfies . This implies both Reed’s result and an independent result of Harutyunyan and Mohar for oriented graphs.

We study the complexity of deciding whether a given digraph D=(V,A) admits a partition (A1,A2) of its arc set such that each of the corresponding digraphs D1=(V,A1) and D2=(V,A2) satisfy some given prescribed property. We mainly focus on the following 15 properties: being bipartite, being connected, being strongly connected, being acyclic (spanning or not necessarily spanning), containing an in-branching, containing an out-branching, having some in-degree (or out-degree) conditions, satisfying some conditions on the number of arcs, being balanced (connected or not) or being a cycle. Combined with previous research, our work leads to a complete classification (in terms of being polynomial or NP-complete) of the complexity of 120 arc-partitioning problems on digraphs.