• P-ISSN 0974-6846 E-ISSN 0974-5645

Indian Journal of Science and Technology


Indian Journal of Science and Technology

Year: 2023, Volume: 16, Issue: Special Issue 3, Pages: 22-29

Original Article

List Coloring Problem: A Heuristic Approach

Received Date:30 January 2023, Accepted Date:11 August 2023, Published Date:20 November 2023


Background/Objectives: List coloring problem is one of the most important generalizations of well-known graph coloring problem. List coloring of a graph is a problem of assigning colors to all vertices of the graph from a pre-defined list of colors for every vertex in such a way that no two adjacent vertices share the same color. In this process, the highest color assigned to a vertex is called span. The objective of the list coloring problem is to minimize this span. Methods: In this study, two heuristic methods are proposed to solve this problem namely: a greedy randomize adaptive search heuristic and a simple greedy heuristic. Findings: Computational experiments on randomly generated graphs show that both the proposed heuristics are capable of obtaining optimal results. It is also observed that greedy randomize adaptive search heuristic performed well as compared to the other one. Comparison with other state-of-art algorithms reveals that both the proposed heuristics have obtained better results for larger graphs in a reasonable time. Novelty: The origin of list coloring problem is very old, still its solving procedures are limited to mostly exact algorithms. Moreover, there is no heuristic available for LCP for general graphs having vertex size more than 150. This paper is an attempt to develop heuristics/metaheuristics for solving this problem for larger graphs in a reasonable time which is not possible with exact methods.

Keywords: Graph Coloring, List coloring, GRASP


  1. Sankar JR, Felix A, Mokeshrayalu G, Nathan MMS. A survey: List coloring problem. International Journal of Control Theory and Applications. 2016;9(36):245–249. Available from: https://research.vit.ac.in/publication/a-survey-list-coloring-problem-1
  2. Laurent B, Hao JK. List-graph colouring for multiple depot vehicle scheduling. International Journal of Mathematics in Operational Research. 2009;1(1-2):228–245. Available from: https://doi.org/10.1504/IJMOR.2009.022883
  3. Bonomo F, Durán G, Marenco J. Exploring the complexity boundary between coloring and list-coloring. Annals of Operations Research. 2009;169(1):3–16. Available from: https://doi.org/10.1007/s10479-008-0391-5
  4. Lucci M, Nasini G, Severín D. A Branch and Price Algorithm for List Coloring Problem. Electronic Notes in Theoretical Computer Science. 2019;346:613–624. Available from: https://doi.org/10.1016/j.entcs.2019.08.054
  5. Mukherjee S, Grover. A Grover Search-Based Algorithm for the List Coloring Problem. IEEE Transactions on Quantum Engineering. 2022;3:1–8. Available from: https://doi.org/10.1109/TQE.2022.3151137
  6. Molloy M. The list chromatic number of graphs with small clique number. Journal of Combinatorial Theory, Series B. 2019;134:264–284. Available from: https://doi.org/10.1016/j.jctb.2018.06.007
  7. Cranston DW, Coloring. Coloring, List Coloring, and Painting Squares of Graphs (and Other Related Problems) The electronic journal of combinatorics. 2023;30(2):1–42. Available from: https://doi.org/10.37236/10898


© 2023 Srivastava et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. Published By Indian Society for Education and Environment (iSee)


Subscribe now for latest articles and news.