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.
[1] Bondy, J.A., Murty, U.S.R.: Graph Theory, 244th edn. GTM, Springer, London (2008)
[2] Gallai, T.: Transitiv orientierbare Graphen. Acta Math. Hungar. 18, 25–66 (1967)
[3] Chvátal, V., Sbihi, N.: Recognizing claw-free Berge graphs. J. Combin. Theory Ser. B. 44, 154–176 (1988)
[4] Maffray, F., Reed, B.A.: A description of claw-free perfect graphs. J. Combin. Theory Ser. B. 75, 134–156 (1999)
[5] Sun, L.: Two classes of perfect graphs. J. Combin. Theory Ser. B. 53, 273–292 (1991)
[6] Joos, F., Le, V.B., Rautenbach, D.: Forests and trees among Gallai graphs. Discrete Math. 338, 190–195 (2015)
[7] Le, V.B.: Mortality of iterated Gallai graphs. Period. Math. Hungar. 27, 105–124 (1993)
[8] Le, V.B.: Gallai graphs and anti-Gallai graphs. Discret. Math. 159, 179–189 (1996)
[9] Anand, P., Escuadro, H., Gera, R., Hartke, S.G., Stolee, D.: On the hardness of recognizing triangular line graphs. Discret. Math. 312, 2627–2638 (2012)
[10] Lakshmanan, S.A.: Characterization of some special classes of the Gallai and the anti-Gallai graphs. Discourse 1, 85–89 (2013)
[11] Lakshmanan, S.A., Rao, S.B., Vijayakumar, A.: Gallai and anti-Gallai graphs of a graph. Math. Bohem. 132, 43–54 (2007)
[12] Palathingal, J.J., Lakshmanan, S.A.: Gallai and anti-Gallai graph operators. Electron. Notes Discret. Math. 63, 447–453 (2017)
[13] Andrews, E., Lumduanhom, C., Laforge, E., Zhang, P.: On proper-path colorings in graphs. J. Combin. Math. Comb. Comput. 97, 189–207 (2016)
[14] Borozan, V., Fujita, S., Gerek, A., Magnant, C., Manoussakis, Y., Montero, L., Tuza, Z.: Proper connection of graphs. Discret. Math. 312, 2550–2560 (2012)
[15] Li, X., Wei, M., Yue, J.: Proper connection number and connected dominating sets. Theoret. Comput. Sci. 607, 480–487 (2015)
[16] Huang, F., Li, X., Wang, S.: Upper bound of proper connection number of graphs. J. Comb. Optim. 34, 165–170 (2017)
[17] Laforge, E., Lumduanhom, C., Zhang, P.: Characterizations of graphs having large proper connection numbers. Discuss. Math. Graph Theory. 36, 439–453 (2016)
[18] Caro, Y., Lev, A., Roditty, Y., Tuza, Z., Yuster, R.: On rainbow connection. Electron. J. Combin. 15, Research paper 57 (2008)
[19] Chartrand, G., Johns, G.L., McKeon, K.A., Zhang, P.: Rainbow connection in graphs. Math. Bohem. 133, 85–98 (2008)
[20] Li, X., Magnant, C.: Properly colored notions of connectivity—a dynamic survey. Theory Appl. Graphs. 1, 2 (2015)
[21] Huang, F., Yuan, J.J.: On strong proper connection number of cubic graphs. Discret. Appl. Math. 265, 104–119 (2019)
[22] Garey, M.R., Johnson, D.S.: Computers andIntractability:AGuide to the Theory ofNP-Completeness. Freeman, San Francisco, CA (1979)
[23] Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1, 237–267 (1976)
[24] Dirac, G.A.: On rigid circuit graphs. Abh. Math. Semin. Univ. Hambg. 25, 71–76 (1961)
