Graph colorings and digraph subdivisions

  • Phablo F. S. Moura
  • Yoshiko Wakabayashi


This paper presents our studies on three vertex coloring problems on graphs and on a problem concerning subdivision of digraphs. Given an arbitrarily colored graph G, the convex recoloring problem consists in finding a (re)coloring that minimizes the number of color changes and such that each color class induces a connected subgraph of G. This problem is motivated by its application in the study of phylogenetic trees in Bioinformatics. In the kfold coloring problem one wishes to cover the vertices 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) sets. The proper orientation problem consists in orienting the edges of a graph so that adjacent vertices have different in-degrees and the maximum in-degree is minimized. Our contributions in these problems are in terms of algorithms, hardness, and polyhedral studies. Finally, we investigate a long-standing conjecture of Mader on subdivision of digraphs: 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 give evidences for this conjecture by proving it holds for classes of acyclic digraphs.

Como Citar

Selecione um Formato
MOURA, Phablo F. S.; WAKABAYASHI, Yoshiko. Graph colorings and digraph subdivisions. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 31. , 2018, Natal. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . ISSN 2763-8820. DOI: