A network N is formed by a (multi)digraph D together with a capacity function u : A ( D ) → R + , and it is denoted by N = ( D , u ) . A flow on N is a function x : A ( D ) → R + such that x ( a ) ≤ u ( a ) for all a ∈ A ( D ), and it is said to be k -splittable if it can be decomposed into up to k paths. We say that a flow is λ -uniform if its value on each arc of the network with positive flow value is exactly λ , for some λ ∈ R + * . We consider the problem of decomposing a flow over an arc-coloured network with minimum cost, that is, with minimum sum of the cost of its paths, where the cost of each path is given by its number of colours. We show that this problem is NP -Hard for general flows on networks. When we restrict the problem to λ -uniform flows, we show that it can be solved in polynomial time for networks with at most two colours. Moreover, we prove that it is NP -Hard for general networks with three colours and for acyclic networks with at least five colours.

We define the family of Maya-Tupi graphs as those graphs that admit a partition ( A, B) of their vertex sets such that A induces a complete multipartite graph where each part has size at most two, and B induces a graph where every connected component is K 1 or K 2 . The family of Maya-Tupi graphs is self complementary, generalizes split graphs, falls into the sparse-dense partitioning schema and is characterized by finitely many forbidden induced subgraphs. Unfortunately, our computational experiments show that the number of minimal forbidden induced subgraphs to characterize Maya-Tupi graphs is greater than 2000. In this work, we study Maya-Tupi graphs when restricted to some well-known graph classes. We find characterizations in terms of minimal forbidden induced subgraphs for disconnected graphs, trees and cographs; our results imply linear time certifying recognition algorithms for Maya-Tupi graphs within these classes. We also show that Maya-Tupi graphs can be recognized in O( n 3 )-time in C 4 -free graphs and in graphs with bounded neighborhood diversity.

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.

A graph G is strict quasi parity (SQP) if every induced subgraph of G that is not a clique contains a pair of vertices with no odd chordless path between them (an even pair). Hougardy conjectured that the minimal forbidden subgraphs for the class of SQP graphs are the odd chordless cycles, the complements of odd or even chordless cycles, and some line-graphs of bipartite graphs. Here we prove this conjecture for planar graphs. We also give a constructive characterization of all the planar minimal forbidden subgraphs for the class of SQP graphs.