Revisit the Coloring Problem of Gallai Graphs

Abstract

Given a graph $G=(V,E)$, the Gallai graph of G, denoted by $\Gamma (G)$, is the graph with vertex set E in which two edges e and f of G are adjacent in $\Gamma (G)$ iff e and f are adjacent in G but do not span a triangle in G. The Gallai chromatic number of G, denoted by $\chi ^{\Gamma }(G)$, is defined to be the chromatic number of $\Gamma (G)$. It is known that the problem for determining $\chi ^{\Gamma }(G)$ is NP-complete for a general graph G. In this paper, we study the Gallai chromatic number of graphs and relate our research with some parameters about edge coloring of graphs, such as PC number, SPC number, as well as chromatic index. For the (k, r)-star, we determine its PC number, SPC number, Gallai chromatic number, and chromatic index, and show that these parameters differ considerably in a sense. Then we show that the problem for determining $\chi ^{\Gamma }(G)$ is still NP-complete even when G is a 3-regular graph, a near-complete graph or a chordal graph of diameter 5. Our result also implies that the problem for determining the SPC number of a graph G is NP-complete when G is a chordal graph of diameter 5.