Riste Škrekovski - The Odd Coloring

Povzetek/Abstract

A proper vertex coloring φ of a graph G is said to be odd if for each non-isolated vertex x∈V(G), there exists a color c such that φ−1(c)∩N(x) is odd-sized, i.e. in the neighborhood of each vertex some color appears an odd number of times. The minimum number of colors in any odd coloring of G, denoted χo(G), is the odd chromatic number. Odd colorings were recently introduced in [M. Petruševski, R. Škrekovski: Colorings with neighborhood parity condition, Discret. Appl. Math. 321 385-391 (2022)].

In the talk we discuss various basic properties of this new graph parameter, establish several upper bounds, several characterizations, and pose some questions and problems. We will also consider another new and related coloring, so called the proper conflict-free coloring.

This is a joint work with Mirko Petruševski from Skopje, Macedonia & Yair Caro from Haifa, Israel.

Abstract in pdf version in attachment.