Proper vertex coloring with odd occurrence - Probabilistic approach
Time: 14:00 -- Location: LRI, 445
summary: In graph theory, a graph coloring is an assignment of colors to elements of a graph subject to certain constraints.
A vertex coloring is said to be proper if any pair of two adjacent vertices are assigned distinct colors.
For a graph G, the chromatic number χ(G) is the minimum number of colors k such that there is a proper coloring using at most k colors.
Using a greedy algorithm, one can trivially observe that χ(G) is at most Δ(G)+1, where Δ(G) is the maximum degree of G.
In this talk, we consider odd colourings, that generalise proper colourings with the addition of the constraint that every vertex of positive degree must have a color appearing an odd number of times in its neighborhood. It is conjectured that the odd chromatic number χₒ(G) is at most Δ(G)+1. We prove several relative results which indicates that the gap between χₒ(G) and Δ(G) should be at most O(log Δ), by some probabilistic methods.