Tesis Doctoral
DOI
10.11606/T.45.2017.tde-23052017-100619
Documento
Autor
Nombre completo
Phablo Fernando Soares Moura
Dirección Electrónica
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2017
Director
Tribunal
Wakabayashi, Yoshiko (Presidente)
Campêlo Neto, Manoel Bezerra
Figueiredo, Celina Miraglia Herrera de
Mota, Guilherme Oliveira
Souza, Cid Carvalho de
Título en inglés
Graph colorings and digraph subdivisions
Palabras clave en inglés
Column generation
Computational complexity
Convex recoloring
Digraph subdivision
Graph coloring
Graph orientation
Inapproximability
Polyhedral study
Resumen en inglés
The vertex coloring problem is a classic problem in graph theory that asks for a partition of the vertex set into a minimum number of stable sets. This thesis presents our studies on three vertex (re)coloring problems on graphs and on a problem related to a long-standing conjecture on subdivision of digraphs. Firstly, we address the convex recoloring problem in which an arbitrarily colored graph G is given and one wishes to find a minimum weight recoloring such that each color class induces a connected subgraph of G. We show inapproximability results, introduce an integer linear programming (ILP) formulation that models the problem and present some computational experiments using a column generation approach. The k-fold coloring problem is a generalization of the classic vertex coloring problem and consists in covering the vertex set of a graph by a minimum number of stable sets in such a way that every vertex is covered by at least k (possibly identical) stable sets. We present an ILP formulation for this problem and show a detailed polyhedral study of the polytope associated with this formulation. The last coloring problem studied in this thesis is the proper orientation problem. It consists in orienting the edge set of a given graph so that adjacent vertices have different in-degrees and the maximum in-degree is minimized. Clearly, the in-degrees induce a partition of the vertex set into stable sets, that is, a coloring (in the conventional sense) of the vertices. Our contributions in this problem are on hardness and upper bounds for bipartite graphs. Finally, we study a problem related to a conjecture of Mader from the eighties on subdivision of digraphs. This conjecture states that, for every acyclic digraph H, there exists an integer f(H) such that every digraph with minimum out-degree at least f(H) contains a subdivision of H as a subdigraph. We show evidences for this conjecture by proving that it holds for some particular classes of acyclic digraphs.
Título en portugués
Colorações de grafos e subdivisões de digrafos
Palabras clave en portugués
Coloração de grafos
Geração de colunas
Orientação de grafos
Poliedro
Recoloração convexa
Subdivisão de digrafos
Resumen en portugués