A Novel Heuristic for Estimating Two-Colorability for Conflict-Free Coloring in Simple Graphs

Graph coloring is an important subject in combinatorics and algorithm theory. Conflict-free coloring is one possible generalization of traditional graph coloring. Conflict-free coloring of graphs induced by geometric shapes like intervals on the line or disks on the plane finds practical applications in the cellular network domain for problems ranging from radio frequency identification to frequency assignment. For instance, in the latter case, the goal of an algorithm would be to minimize the number of assigned frequencies, that is, reuse frequencies as much as possible. This, in effect, translates to evaluating the conflict-free chromatic number, the minimum number of colors that can be used to minimize the number of assigned frequencies. This paper proposes a novel heuristic to check if the graph can be colored, on the principles of conflict-free coloring in a closed neighborhood, using only two colors. If so, then the heuristic also returns the required color scheme for the given graph. To the best of the authors’ knowledge, this is the first heuristic approach proposed for the two-color conflict-free case. The performance of the proposed heuristic is studied on a large number of test instances using the Erdos–Renyi graph model.

Authors and Affiliations

1. Dayalbagh Educational Institute, Agra, India

   Rishabh Singhal, Ayushi Sengar, V. Prem Prakash & Mayank Agrawal

Corresponding author

Correspondence to Rishabh Singhal .

Editors and Affiliations

1. Department of Mechanical and Industrial Engineering, Indian Institute of Technology Roorkee, Roorkee, India

   V. H. Saran

2. Department of Electrical Engineering, Indian Institute of Technology (BHU) Varanasi, Varanasi, India

   Rakesh Kumar Misra

Reprints and permissions

© 2021 Springer Nature Singapore Pte Ltd.

Policies and ethics