Combining proper and square colorings
Borut Luzar

Abstract

Proper colorings of graphs with additional distance constraints are an
attractive topic in both settings: the vertex and the edge
coloring. In particular, when we require that two vertices are colored
differently if they are at distance at most 2, we are essentially
coloring the square of a graph. Similarly, in a proper coloring of
edges where two edges are colored differently as soon as they are
adjacent or two of their endvertices are at distance 1, we are
coloring the square of the line graph of a graph. We usually refer to
the former as the square coloring and to the latter as the strong edge
coloring.

Motivated by the notion of S-packing coloring, we will consider
colorings with two types of colors: proper colors, which will be
allowed to appear on two non-adjacent objects (regarding the
setting---vertex or edge coloring), and strong colors, with which we
will be able to color objects at distance at least 3 (in the edge
coloring setting, the distance between two edges is taken as the
distance between the corresponding vertices in the line graph). This
combination of color types positions us in between the proper and the
square colorings, which in most of the cases makes determination of
the corresponding chromatic indices harder, but it also reveals
several nice properties.

In the talk, we will focus mainly to coloring subcubic graphs and
review recent results and the most interesting open problems on the
topic in the vertex and the edge coloring settings.