Given a graph G=(V,E),the Gallai graph of G,denoted by Γ(G),is the graph with vertex set E in which two edges e and f of G are adjacent in Γ(G)iff e and f are adjacent in G but do not span a triangle in G.The Gallai...Given a graph G=(V,E),the Gallai graph of G,denoted by Γ(G),is the graph with vertex set E in which two edges e and f of G are adjacent in Γ(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 χ^(Γ)(G),is defined to be the chromatic number of Γ(G).It is known that the problem for determining χ^(Γ)(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 χ^(Γ)(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.展开更多
基金supported by the National Natural Science Foundation of China(Nos.12071442 and 11971228)the Fundamental Research Funds for the Central Universities(No.020314380035).
文摘Given a graph G=(V,E),the Gallai graph of G,denoted by Γ(G),is the graph with vertex set E in which two edges e and f of G are adjacent in Γ(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 χ^(Γ)(G),is defined to be the chromatic number of Γ(G).It is known that the problem for determining χ^(Γ)(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 χ^(Γ)(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.
