Kalle Eriksson: Single conflict coloring

Abstract

Graph coloring is a classical area of graph theory, dating back to the mid-1800s. In this talk, we explore a more recent variant called single conflict coloring, investigating which graphs are single conflict 2-colorable, bounds on the associated chromatic number, and some probabilistic results. The presentation is based on work from my master’s thesis at Linköping University this spring.