IGL Spring 2020 - Royal Colorings of Graphs

An edge-induced vertex coloring is a vertex coloring of a graph that is obtained from an edge coloring via some specific rule. In this project we assign non-empty subsets of {1, 2,..., k} to the edges of a graph, and then color the vertices by the union of the colors of their incident edges. We call this a Royal k-coloring if this edge-induced vertex coloring assigns each vertex a different subset. Our main goal was to explore the smallest k such that a given graph has a Royal k-coloring. We proved that we can reduce this problem to a vertex coloring problem, and with this reduction, we found the minimum k for some nice classes of graphs, such as stars, paths and binary trees.