Backbone Coloring Problems

Abstract

Let H be a subgraph of a graph G in a graph pair (G,H). A backbone coloring for a graph pair (G,H) is a vertex coloring of G such that adjacent vertices receive distinct colors, adding a condition that colors assigned to adjacent vertices in a subgraph H must differ by at least 2.
This article presents the brief history of backbone coloring problems and some related colorings. Then some researches of backbone coloring problems is proposed for example, L(2,1)-labeling, λ-backbone coloring and list backbone coloring. Moreover, topics of future researches are presented.