LIST COLORING OF BLOCK GRAPHS AND COMPLETE BIPARTITE GRAPHS

  • Albert Khachik Sahakyan Chair of Discrete Mathematics and Theoretical Informatics, Faculty of Informatics and Applied Mathematics, Yerevan State University, Armenia
Keywords: block graph, complete bipartite graphs, list coloring, edge coloring, NP-complete, dynamic programming, bipartite matching.

Abstract

List coloring is a vertex coloring of a graph where each vertex can be restricted to a list of allowed colors. For a given graph G and a set L(v) of colors for every vertex v, a list coloring is a function that maps every vertex v to a color in the list L(v) such that no two adjacent vertices receive the same color. It was first studied in the 1970s in independent papers by Vizing and by Erdős, Rubin, and Taylor. A block graph is a type of undirected graph in which every biconnected component (block) is a clique. A complete bipartite graph is a bipartite graph with partitions V 1, V 2 such that for every two vertices v_1∈V_1 and v_2∈V_2 there is an edge (v 1, v 2). If |V_1 |=n and |V_2 |=m it is denoted by K_(n,m). In this paper we provide a polynomial algorithm for finding a list coloring of block graphs and prove that the problem of finding a list coloring of K_(n,m) is NP-complete even if for each vertex v the length of the list is not greater than 3 (|L(v)|≤3).

References

West D.B. Introduction to Graph Theory. Prentice-Hall, New Jersey, 1996.

Harary F. Graph Theory. Addison-Wesley Publishing Company, Boston, 1969.

P. Erdős, A.L. Rubin, H. Taylor, Choosability in graphs, Proc. West Coast Conf. on Com- binatorics, Graph Theory and Computing, Congr. Numer. 26, 1979, pp. 125-157.

Vizing, V. G. (1976), "Vertex colorings with given colors", Metody Diskret. Analiz. (In Russian), 29: 3–10

Hougardy, S. (2006). Classes of perfect graphs. Discret. Math., 306, 2529-2571.

Jansen, K., & Scheffler, P. (1997). Generalized coloring for tree-like graphs. Discrete Applied Mathematics, 75(2), 135–155. https://doi.org/10.1016/s0166-218x(96)00085-6

Biró, M., Hujter, M. & Tuza, Z. (1992). Precoloring extension. I. Interval graphs. Discrete Mathematics, 100, 267-279.

Marx, D. (2006). Precoloring extension on unit interval graphs. Discrete Applied Mathematics, 154, 995–1002.

Jansen, K. (1997). The Optimum Cost Chromatic Partition Problem. In G. C. Bongiovanni, D. P. Bovet & G. D. Battista (eds.), CIAC (p./pp. 25-36),: Springer. ISBN: 3-540-62592-5

Bonomo, F., Durán, G. & Marenco, J. (2009). Exploring the complexity boundary between coloring and list-coloring. Ann. Oper. Res., 169, 3-16.

Karp, R. (1972). Reducibility among combinatorial problems. In R. Miller & J. Thatcher (ed.), Complexity of Computer Computations (pp. 85-103). Plenum Press.

Cook, S. A. (1971). The complexity of theorem proving procedures. Proceedings of the Third Annual ACM Symposium (p./pp. 151--158), New York.

Kubale M. Interval vertex-coloring of a graph with forbidden colors. Discret. Math., 74, (1989) 125-136.

Published
2021-08-25
Citations
How to Cite
Albert Khachik Sahakyan. (2021). LIST COLORING OF BLOCK GRAPHS AND COMPLETE BIPARTITE GRAPHS. World Science, (8(69). https://doi.org/10.31435/rsglobal_ws/30082021/7661
Section
Physics and Mathematics
Share