Graph colorings and digraph subdivisions
Phablo F. S. Moura, Yoshiko Wakabayashi · 2018
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 k-fold 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.