Skip to content
Texas A&M University
Mathematics

Algebra and Combinatorics Seminar

Date: March 3, 2023

Time: 3:00PM - 4:00PM

Location: BLOC 302

Speaker: Chun-Hung Liu, Texas A&M University

  

Title: Proper conflict-free coloring and maximum degree

Abstract: A conflict-free coloring of a hypergraph is a coloring on the vertices such that for every hyperedge, some color appears exactly once on the vertices of this edge. This notion is motivated by a frequency assignment problem of cellular networks and is a generalization of a number of variants of coloring notions of graphs. We prove a general upper bound for the number of colors for (proper) conflict-free coloring involving the maximum degree and rank. It provides improvements about linear coloring and star coloring of graphs with bounded maximum degree and addresses a conjecture of Caro, Petrusevski and Skrekovski on proper conflict-free coloring of graphs. They conjectured that for every d \geq 3, every connected graph with maximum degree at most d has a proper conflict-free coloring with d+1 colors. We prove that (1.655083+o(1))d colors suffice. We also prove that the fractional coloring version of this conjecture is asymptotically true. This is joint work with Daniel Cranston.