LIST COLORING OF BLOCK GRAPHS AND COMPLETE BIPARTITE GRAPHS
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.
Views:
492
Downloads:
198
Copyright (c) 2021 Albert Khachik Sahakyan
This work is licensed under a Creative Commons Attribution 4.0 International License.
All articles are published in open-access and licensed under a Creative Commons Attribution 4.0 International License (CC BY 4.0). Hence, authors retain copyright to the content of the articles.
CC BY 4.0 License allows content to be copied, adapted, displayed, distributed, re-published or otherwise re-used for any purpose including for adaptation and commercial use provided the content is attributed.
