Conflict-free colorings of graphs
COM1 Level 3
MR1, COM1-03-19
Abstract:
Given a graph, a conflict-free coloring is an assignment of colors to the vertices such that for every vertex, there is a color that appears exactly once in its neighborhood. The goal of the conflict-free coloring problem is to obtain such a coloring using the smallest number of colors. The problem was introduced in 2002 by Even, Lotker, Ron, and Smorodinsky. The problem is NP-hard and has been studied on various classes of graphs (see the survey by Smorodinsky).
In this talk, we will describe the problem and cover a few results. The talk will be based on some results from the below two papers:
1. Conflict-Free Coloring Bounds on Open Neighborhoods (joint with Sriram Bhyravarapu and Rogers Mathew, Algorithmica 2022)
2. Extremal Results on Conflict-free Coloring (joint with Sriram Bhyravarapu, Shiwali Gupta, and Rogers Mathew, under review)
Brief Bio:
Subrahmanyam Kalyanasundaram is a faculty member at the Department of Computer Science and Engineering, Indian Institute of Technology Hyderabad. His area of research is theoretical computer science, and he has recently been working on structural and algorithmic questions on graphs. More details can be found at https://people.iith.ac.in/subruk/