Given an oriented graph $D$, the inversion of a subset $X$ of vertices consists in reversing the orientation of all arcs with both endpoints in $X$. When the subset $X$ is of size $p$ (resp. at most $p$), this operation is called an $(=p)$-inversion (resp. $(\leq p)$-inversion). Then, an oriented graph is $(=p)$-invertible if it can be made acyclic by a sequence of $p$-inversions. We observe that, for $n=|V(D)|$, deciding whether $D$ is $(=n-1)$-invertible is equivalent to deciding whether $D$ is acyclically pushable, and thus NP-complete. In all other cases, when $p \neq n-1$, we construct a polynomial-time algorithm to decide $(=p)$-invertibility. We then consider the $(= p)$-inversion number, $\text{inv}^{= p}(D)$ (resp. $(\leq p)$-inversion number, $\text{inv}^{\leq p}(D)$), defined as the minimum number of $(=p)$-inversions (resp. $(\leq p)$-inversions) rendering $D$ acyclic. We show that every $(=p)$-invertible digraph $D$ satisfies $\text{inv}^{= p}(D) \leq |A(D)|$ for every integer $p\geq 2$. When $p$ is even, we bound $\text{inv}^{= p}$ by a (linear) function of the feedback arc set number, and rule out the existence of any bounding function for odd $p$. Finally, we study the complexity of deciding whether the $(= p)$-inversion number, or the $(\leq p)$-inversion number, of a given oriented graph is at most a given integer $k$. For any fixed positive integer $p \geq 2$, when $k$ is part of the input, we show that both problems are NP-hard even in tournaments. In general oriented graphs, we prove $W[1]$-hardness for both problems when parameterized by $p$, even for $k=1$. In contrast, we exhibit polynomial kernels in $p + k$ for both problems in tournaments.

A b-greedy colouring is a colouring which is both a b-colouring and a greedy colouring. A z-colouring is a b-greedy colouring such that a b-vertex of the largest colour is adjacent to a b-vertex of every other colour. The b-Grundy number (resp. z-number) of a graph is the maximum number of colours in a b-greedy colouring (resp. z-colouring) of it. In this paper, we study those two parameters. We show that similarly to the z-number, the b-Grundy number is not monotone and can be arbitrarily smaller than the minimum of the Grundy number and the b-chromatic number. We also describe a polynomial-time algorithm that decides whether a given k-regular graph has b-Grundy number (resp. z-number) equal to k+1. We also prove that every cubic graph with no induced 4-cycle has b-Grundy number and z-number exactly 4.

Abstract. The dichromatic number [Formula: see text] of a digraph [Formula: see text] is the least integer [Formula: see text] such that [Formula: see text] can be partitioned into [Formula: see text] directed acyclic digraphs. A digraph is [Formula: see text]-dicritical if [Formula: see text] and each proper subgraph [Formula: see text] of [Formula: see text] satisfies [Formula: see text]. An oriented graph is a digraph with no directed cycle of length 2. For integers [Formula: see text] and [Formula: see text], we denote by [Formula: see text] the minimum number of edges of a [Formula: see text]-dicritical oriented graph on [Formula: see text] vertices. The main result of this paper is a proof that [Formula: see text] together with a construction witnessing that [Formula: see text] for all [Formula: see text]. We also give a construction showing that for all sufficiently large [Formula: see text] and all [Formula: see text], [Formula: see text], disproving a conjecture of Hoshino and Kawarabayashi.

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 →χ (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) → N \ {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) ≠ 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 maxvϵV(G) S(d,w)(v) ≤ k. The semi-proper orientation number of a graph G, denoted by →χs(G), is the least k such that G has a semi-proper k-orientation. In this work, we first prove that →χs(G) ϵ {ω(G) - 1, ω(G)} for every split graph G, and that, given a split graph G, deciding whether →χs(G) = ω(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 →χ(G) ≤ k and →χ(H) = 2k - 2. In the sequel, we show that, for every n ≥ p(p + 1), →χs(Ppn) = [3/2 p], where Ppn is the pth power of the path on n vertices. We investigate further unit interval graphs with no big clique: we show that →χ(G) ≤ 3 for any unit interval graph G with ω(G) = 3, and present a complete characterization of unit interval graphs with →χ(G)= ω(G) = 3. Then, we show that deciding whether →χs(G) = ω(G) can be solved in polynomial time in the class of co-bipartite graphs. Finally, we prove that computing →χ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 →χs(G) but also →χ(G), admits a polynomial kernel when parameterized by the neighbourhood diversity plus the value of the solution. These results imply kernels of size 40(k2) and 0(2kk2), in chordal graphs and split graphs, respectively, for the problem of deciding whether →χs(G) ≤ k parameterized by k. We also present exponential kernels for computing both →χ(G) and →χs(G) parameterized by the value of the solution when G is a cograph. On the other hand, we show that computing →χs(G) does not admit a polynomial kernel parameterized by the value of the solution when G is a chordal graph, unless NP ⊆ coNP/poly.

An $L(p,1)$-labeling of a graph is a function f from the vertex set to the positive integers such that $|f(x)-f(y)|\geqslant p$ if dist$(x,y)=1$ and $|f(x)-f(y)|\geqslant 1$ if dist$(x,y)=2$, where dist$(x,y)$ is the distance between the two vertices x and y in the graph. The span of an $L(p,1)$-labeling f is the difference between the largest and the smallest labels used by f. In 1992, Griggs and Yeh conjectured that every graph with maximum degree $\Delta\geqslant 2$ has an $L(2,1)$-labeling with span at most $\Delta^2$. We settle this conjecture for $\Delta$ sufficiently large. More generally, we show that for any positive integer p there exists a constant $\Delta_p$ such that every graph with maximum degree $\Delta\geqslant \Delta_p$ has an $L(p,1)$-labeling with span at most $\Delta^2$. This yields that for each positive integer p, there is an integer $C_p$ such that every graph with maximum degree $\Delta$ has an $L(p,1)$-labeling with span at most $\Delta^2+C_p$.

A proper edge-coloring with the property that every cycle contains edges of at least three distinct colors is called an acyclic edge-coloring. The acyclic chromatic index of a graph [Formula: see text], denoted [Formula: see text], is the minimum [Formula: see text] such that [Formula: see text] admits an acyclic edge-coloring with [Formula: see text] colors. We conjecture that if [Formula: see text] is planar and [Formula: see text] is large enough, then [Formula: see text]. We settle this conjecture for planar graphs with girth at least 5. We also show that [Formula: see text] for all planar [Formula: see text], which improves a previous result by Fiedorowicz, Haluszczak, and Narayan [Inform. Process. Lett., 108 (2008), pp. 412–417].

We answer in the negative a question of Oporowski and Zhao [Discrete Math., 309 (2009), pp. 2948–2951] asking whether every graph with crossing number at most 5 and clique number at most 5 is 5-colorable. However, we show that every graph with crossing number at most 4 and clique number at most 5 is 5-colorable. We also show some colorability results on graphs that can be made planar by removing a few edges. In particular, we show that, if a graph with clique number at most 5 has three edges whose removal leaves the graph planar, then it is 5-colorable.

Abstract Motivated by a satellite communications problem, we consider a generalized coloring problem on unit disk graphs. A coloring is k‐improper if no more than k neighbors of every vertex have the same colour as that assigned to the vertex. The k‐improper chromatic number χk(G) is the least number of colors needed in a k‐improper coloring of a graph G. The main subject of this work is analyzing the complexity of computing χk for the class of unit disk graphs and some related classes, e.g., hexagonal graphs and interval graphs. We show NP‐completeness in many restricted cases and also provide both positive and negative approximability results. Because of the challenging nature of this topic, many seemingly simple questions remain: for example, it remains open to determine the complexity of computing χk for unit interval graphs. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

A plane graph is ł-facially k-colorable if its vertices can be colored with k colors such that any two distinct vertices on a facial segment of length at most łare colored differently. We prove that every plane graph is 3-facially $11$-colorable. As a consequence, we derive that every 2-connected plane graph with maximum face-size at most 7 is cyclically $11$-colorable. These two bounds are just one higher than those that are proposed by the $(3\l+1)$-conjecture and the cyclic conjecture.

Abstract We consider on‐board networks in satellites interconnecting entering signals (inputs) to amplifiers (outputs). The connections are made via expensive switches, each of which has four available links. The paths connecting inputs to outputs should be link‐disjoint. Some of the input signals, called priorities, must be connected to the amplifiers that provide the best quality of service (that is, to some specific outputs). In practice, amplifiers are prone to fail, and the faults cannot be repaired. Therefore, extra outputs have to be built into the network to ensure that every input can be routed to operational outputs. Given three integers, n, p, and f, we would like to design a low‐cost network (where the network cost is proportional to the total number of switches) such that it is possible to route all n inputs to n operational amplifiers, and to route the p priorities to the p best quality amplifiers for any set of f faulty and p best‐quality amplifiers. Let R(n, p, f) be the minimum number of switches of such a network. We prove here that $R(n,p,f)\leq{{n+f}\over{2}}\lceil\log_2p\rceil+{{5}\over{2}}(n-p)+g(f)$ with g a function depending only on f. We then compute R(n, p, f) exactly for a few small values of p and f. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 47(1), 9–25 2006

Abstract In this article, we introduce the Push Tree problem, which exposes the tradeoffs between the use of push and pull mechanisms in information distribution systems. One of the interesting features of the Push Tree problem is that it provides a smooth transition between the minimum Steiner Tree and the Shortest Path problems. We present initial complexity results and analyze heuristics. Moreover, we discuss what lessons can be learned from the static and deterministic Push Tree problem for more realistic scenarios characterized by high uncertainty and changing information request and update patterns. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(4), 281–291 2004

In this paper, we introduce the Push Tree problem which contains elements from both the Steiner Tree and the Shortest Path problem. The Push Tree problem deals with the trade-offs between the push and pull mechanisms used in information distribution and retrieval. We present some initial complexity results and analyse several heuristics. Moreover, we discuss what lessons can be learned from the static and deterministic Push Tree problem for more realistic scenarios characterised by high uncertainty and changing information request and update patterns.