Gallai graphs and anti-Gallai graphs

✍ Scribed by Van Bang Le

• Book ID: 103061435
• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 614 KB
• Volume: 159
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00109-a

✦ Synopsis

The Gallai graph and the anti-Gallai graph of a graph G have the edges of G as their vertices. Two edges of G are adjacent in the Gallai graph of G if they are incident but do not span a triangle in G; they are adjacent in the anti-Gallai graph of G if they span a triangle in G. In this paper we show: The Four Color Theorem can be equivalently stated in terms of anti-Gallai graphs; the problems of determining the clique number, and the chromatic number of a Gallai graph are NP-complete. Furthermore, we discuss the relation of Gallai graphs to the theory of perfect graphs. A characterization of Gallai graphs and anti-Gallai graphs is also given.