Structural and complexity studies in inversions and colouring heuristics of (oriented) graphs

Abstract

This thesis is divided in two parts, where the first one concerns the inversion number of oriented graphs. Let D be an oriented graph. The inversion of a set X of vertices in D consists in reversing the direction of all arcs with both extremities in X. The inversion number of D, denoted by inv(D), is the minimum number of inversions needed to make D acyclic. We studied the relation between the inversion number and other parameters related to problems of FEEDBACK ARC SET and FEEDBACK VERTEX SET. We denote by τ(D) (resp. τ′ (D)), the size of a minimum set of vertices (resp. arcs) whose removal makes D acyclic, that is, the minimum size of a feedback vertex set (resp. feedback arc set). For a digraph D, we denote by ν(D), the maximum size of a disjoint set of cycles of D. We show that inv(D) ≤ τ′(D), inv(D) ≤ 2τ(D) and that there exists a function g such that inv(D) ≤ g(ν(D)) and g(1) ≤ 4. For two oriented graphs L and R, the dijoin from L to R, denoted by L → R, is the oriented graph formed by the disjoint union of L and R along with the set of all possible arcs from the vertices of L to those in R. We conjecture that inv(L → R) = inv(L) +inv(R), for any two oriented graphs L and R. This would imply that the first two inequalities are tight. We prove this conjecture when inv(L) ≤ 1 and inv(R) ≤ 2 and when inv(L) = inv(R) = 2 and L and R are strongly connected. We then consider the complexity of deciding whether inv(D) ≤ k for a given oriented graph D. We show that it is NP-complete for k = 1, which together with the above conjecture would imply that it is NP-complete for every k. This contrasts with a result of Belkhechine et al. (BELKHECHINE et al., 2010) which states that deciding whether inv(T) ≤ k for a given tournament T is polynomial-time solvable. The second part of this work is about b-greedy colourings and z-colourings. A b-vertex in a proper colouring is a vertex that has at least one neighbour of every other colour. If in a proper colouring there is a b-vertex of each colour, we say that it is a b-colouring. A greedy colouring is a proper colouring in which every vertex is greedy, that is, it has at least one neighbour of every colour smaller than its own. In its turn, a b-greedy colouring is a proper 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 part, we study those two parameters. We show that they are not monotone and that they can be arbitrarily smaller than the minimum of the Grundy number and the b-chromatic number. We prove that it is NP-hard to compute each of those parameters. However, we 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, except for the Petersen graph, every cubic graph with no induced 4-cycle has b-Grundy number and z-number exactly 4. Finally, we present a summary of other topics involving flows studied during this PhD.