Graph colorings and digraph subdivisions
Resumo
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.
Referências
Araujo, J., Cohen, N., de Rezende, S. F., Havet, F., and Moura, P. F. (2015). On the proper orientation number of bipartite graphs. Theoretical Computer Science, 566(0):59–75.
Araujo, J., Havet, F., Sales, C. L., and Silva, A. (2016). Proper orientation of cacti. Theoretical Computer Science, 639:14–25.
Bar-Yehuda, R., Kutiel, G., and Rawitz, D. (2016). 1.5-approximation algorithm for the 2-convex recoloring problem. In Proceedings of the 26th International Workshop, IWOCA 2015, Verona, Italy, October 5-7, 2015, Revised Selected Papers, pages 299–311. Springer International Publishing.
Campêlo, M., Moura, P. F., and Santos, M. C. (2013). On the representatives k-fold coloring polytope. Electronic Notes in Discrete Mathematics, 44:239–244. Proceedings of LAGOS’13 – VII Latin-American Algorithms, Graphs and Optimization Symposium.
Campêlo, M., Moura, P. F., and Santos, M. C. (2016). Lifted, projected and subgraph-induced inequalities for the representatives k-fold coloring polytope. Discrete Optimization, 21:131–156.
Campêlo, M. B., Huiban, C. G., Sampaio, R. M., and Wakabayashi, Y. (2014). Hardness and inapproximability of convex recoloring problems. Theor. Comp. Sci., 533:15–25.
Kanj, I. A. and Kratsch, D. (2009). Convex recoloring revisited: Complexity and exact algorithms. In Proceedings of the 15th Annual International Conference on Computing and Combinatorics, COCOON ’09, pages 388–397.
Knox, F., González Hermosillo de la Maza, S., Mohar, B., and Linhares Sales, C. (2016). Proper Orientations of Planar Bipartite Graphs. ArXiv e-prints.
Mader, W. (1967). Homomorphieeigenschaften und mittlere Kantendichte von Graphen. Mathematische Annalen, 174:265–268.
Mader, W. (1985). Degree and local connectivity in digraphs. Combinat., 5(2):161–165.
Moura, P. F. and Wakabayashi, Y. (2017). Strong intractability of generalized convex recoloring problems. Electronic Notes in Discrete Mathematics, 62:93 – 98. LAGOS’17 - IX Latin and American Algorithms, Graphs and Optimization.
Moura, P. F. S. (2017). Graph colorings and digraph subdivisions. PhD thesis, Instituto de Matemática e Estatística, Universidade de São Paulo. [link].
