Gallai graphs and anti-Gallai graphs (Q1126196)

The Gallai graph \(\Gamma(G)\) and the anti-Gallai graph \(\Delta(G)\) of a graph \(G\) are spanning subgraphs of the line graph \(L(G)\) of \(G\). Both graphs have the edges of \(G\) as their vertices and two edges of \(G\) are adjacent vertices in \(\Gamma(G)\) if they are incident to a common vertex in \(G\) and if no triangle of \(G\) contains both edges. The edge set of \(\Delta(G)\) consists of all edges of \(L(G)\) not contained in \(\Gamma(G)\), i.e. two edges of \(G\) are adjacent vertices in \(\Delta(G)\) if there is a triangle in \(G\) containing both edges. The author presents a characterization of Gallai graphs and anti-Gallai graphs and he provides some properties and applications of such graphs. He proves that the four colour theorem is equivalent to the statement ``for each planar graph, the chromatic number and the clique number of its anit-Gallai graph are equal.'' Moreover, he verifies Berge's perfect graph conjecture (a graph is perfect if and only if it does not contain a cycle of odd length at least five or the complement of such a cycle as an induced subgraph) for anti-Gallai graphs and for a certain class of Gallai graphs and he presents a conjecture on Gallai graphs which is weaker than the perfect graph conjecture but stronger than the Lovász perfect graph theorem (a graph is perfect if and only if its complement is perfect). Finally, he proves that the problems of determining the clique number and the chromatic number of a Gallai graph are NP-complete.