A conflict-free coloring of a graph G is a vertex coloring in which every vertex has a color that appears exactly once in its neighborhood. The minimum number of colors required is called the conflict-free chromatic number of G. In this talk, we first show that every planar graph admits a conflict-free coloring using at most five colors. We then present a polynomial-time algorithm for biconvex graphs, a subclass of bipartite graphs, based on a multichain ordering, a structural technique that may also prove useful in designing algorithms for other graph problems.
Bio: I am an Assistant Professor in the Department of Computer Science and Engineering at IIT Guwahati. Before joining IIT Guwahati, I spent three years as a postdoctoral researcher at the Institute of Mathematical Sciences (IMSc), Chennai. I received my PhD from IIT Hyderabad in 2016.
