Algebra and Combinatorics Seminar

Date: April 5, 2024

Time: 3:00PM - 3:50PM

Location: BLOC 302

Speaker: Chun-Hung Liu, TAMU

Title: Asymptotically optimal proper conflict-free coloring of bounded maximum degree graphs

Abstract: Every graph of maximum degree d has a coloring with d+1 colors such that no two adjacent vertices receive the same color. Caro, Petrusevski, Skrekovski conjectured that if d >2, then one can always choose such a proper (d+1)-coloring such that for every non-isolated vertex, some color appears on its neighborhood exactly once. We prove that this conjecture holds asymptotically: every graph of maximum degree d has a proper coloring with (1+o(1))d colors such that for every non-isolated vertex, some color appears on its neighborhood exactly once. Joint work with Bruce Reed.