LIST COLORING OF BLOCK GRAPHS AND COMPLETE BIPARTITE GRAPHS
Open Access
- 25 August 2021
- journal article
- Published by RS Global Sp. z O.O. in World Science
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).Keywords
This publication has 10 references indexed in Scilit:
- Exploring the complexity boundary between coloring and list-coloringAnnals of Operations Research, 2008
- Classes of perfect graphsDiscrete Mathematics, 2006
- Precoloring extension on unit interval graphsDiscrete Applied Mathematics, 2006
- Generalized coloring for tree-like graphsDiscrete Applied Mathematics, 1997
- The optimum cost chromatic partition problemLecture Notes in Computer Science, 1997
- Precoloring extension. I. Interval graphsDiscrete Mathematics, 1992
- Interval Vertex-Coloring of a Graph With Forbidden ColorsPublished by Elsevier BV ,1989
- Reducibility among Combinatorial ProblemsPublished by Springer Science and Business Media LLC ,1972
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971
- GRAPH THEORYPublished by Defense Technical Information Center (DTIC) ,1969