DMS Combinatorics Seminar

Speaker: James Anderson (Georgia Tech)

Title: The forb-flex method for odd coloring and proper conflict-free coloring of planar graphs 

Abstract: Odd coloring (resp, PCF coloring) is a stricter form of proper vertex coloring in which every nonisolated vertex is required to have a color in its neighborhood with odd multiplicity (resp, with multiplicity 1). 

We introduce a new tool useful for these colorings, based on greedy coloring, which we call the forb-flex method. Combining this with the discharging method allows us to prove \(\chi_{\mathsf{PCF}}(G) \leq 4\) for planar graphs of girth at least 11, and \(\chi_{\mathsf{o}}(G) \leq 4\) for planar graphs of girth at least 10, improving upon the recent works of Cho, Choi, Kwon, and Park. (We will give a brief overview of the discharging method, so no prior knowledge of discharging is required).