Título: Structural and complexity studies in inversions and colouring

heuristics of (oriented) graphs

Data: 25/05/2023

Horário: 13h00

Local: Sala de Seminários - Bloco 952

Resumo:

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 making a digraph acyclic such as CYCLE ARC TRANSVERSAL (or F EEDBACK ARC SET) and CYCLE TRANSVERSAL (or FEEDBACK VERTEX SET). The cycle transversal (resp. cycle arc-transversal) number of a digraph D, denoted by τ(D) (resp. τ′(D)), is the size of a minimum set of vertices (resp. arcs) whose removal makes D acyclic. The cycle packing number of D, denoted by ν(D), is the maximum size of a disjoint set of cycles of D. We show that inv(D) ≤ τ′(D), inv(D) ≤ 2τ(D) and there exists a function g such that inv(D) ≤ g(ν(D)), where ν(D). We conjecture that for any two oriented graphs L and R, inv(L → R) = inv(L) + inv(R) where L → R is the dijoin of 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 also show that the function g of the third inequality satisfies g(1) ≤ 4. 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-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 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.

Banca examinadora:

• Prof.ª Dr.ª Ana Karolinna Maia de Oliveira (MDCC/UFC) - Orientadora
• Prof.ª Dr.ª Cláudia Linhares Sales (MDCC/UFC) - Coorientadora
• Prof. Dr. Júlio César Silva Araújo (MDCC/UFC)
• Prof. Dr. Thiago Braga Marcilon (UFCA)
• Prof.ª Dr.ª Celina Miraglia Herrera de Figueiredo (UFRJ)
• Prof. Dr. Frédéric Havet (Inria, CNRS/França)