Relaxations of Square Coloring

Abstract

A square coloring of a graph G is a proper coloring of G such that two vertices at distance at most 2 receive distinct colors. After Wegner’s paper in 1977, a square coloring has been an interesting object of many researchers and various relaxations have been introduced. Proper conflict-free coloring and odd coloring are relaxations of square coloring, which are introduced recently and attracted great interest between researchers. In this thesis, we introduce two new concepts of colorings related to proper conflict-free coloring and odd coloring, where they are not only variants of proper conflict-free coloring or odd coloring but also relaxations of square coloring. A proper h-conflict-free coloring of a graph G is a proper coloring of G such that for each vertex v, there are min{degG(v), h} colors appearing uniquely in its neighbor- hood. We obtain an upper bound for the proper h-conflict-free chromatic number of G in linear terms of ∆(G). In addition, we introduce a notion of strong odd coloring which is a proper coloring of G such that for each vertex each color in its neighborhood appears an odd number of times, and then explore observations related to it. keywords : square coloring, odd coloring, proper conflict-free coloring, strong odd coloring