Aspects of parametrized complexity and analogous problems in list coloring of graphs and their variations

• Simone Gama UFAM
• Rosiane de Freitas UFAM
• Ueverton Souza UFF

DOI: https://doi.org/10.5753/etc.2019.6402

Abstract

List coloring is a generalization of the classical vertex coloring problem in graphs. Such a problem has some variations, among them the coloring. In this work, we show the reducibility of the list-coloring problem, coloring and pre-coloring extended, to better provide an analysis of coloring under the parameterized complexity, where it is FPT when parametrized by vertex cover and color lists. We also present the correctness proof of a polynomial algorithm for coloring, from the literature, in complete bipartite graphs.

Keywords: algorithms, bipartite graphs, parameterized complexity, polynomial proof

References

Bondy, A. and Murty, U. S. R. (2011). Graph Theory. Graduate Texts in Mathematics. Springer London.

Centeno, C. C. (2012). A convexidade P3 para grafos não direcionados. PhD thesis, UFRJ.

Harari, F. and Holzmann, C. (1974). Line graphs of bipartiti graphs. 1:19–22.

Harary, F., Nieminen, J., et al. (1981). Convexity in graphs. Journal of Differential Geometry, 16(2):185–190.

Maffray, F. and Reed, B. (1999). A description of claw-free perfect graphs. Journal of Combinatorial Theory, 75:134–156.

Moon, J. W. (1972). Embedding tournaments in simple tournaments. Discrete Mathematics, 2(4):389 – 395.

Pelayo, I. M. (2013). Geodesic Convexity in Graphs. SpringerBriefs in Mathematics. Springer New York.

Santhakumaran, A. and John, J. (2007). Edge geodetic number of a graph. Journal of Discrete Mathematical Sciences Cryptography, 3.

Soares, P. R. (2008). Um estudo das estruturas de grafos sem garras. Master’s thesis, UFRJ.

Yannakakis, M. and Gavril, F. (1980). Edge dominating sets in graphs. SIAM Journal on Applied Mathematics, 38(3):364–372.