Gallai and anti-Gallai graphs of a graph
Aparna Lakshmanan S, Snehal B. Rao, A. Vijayakumar · Mathematica Bohemica · 2007
The paper deals with graph operators—the Gallai graphs and the anti-Gallai graphs. We prove the existence of a finite family of forbidden subgraphs for the Gallai graphs and the anti-Gallai graphs to be $H$-free for any finite graph $H$. The case of complement reducible graphs—cographs is discussed in detail. Some relations between the chromatic number, the radius and the diameter of a graph and its Gallai and anti-Gallai graphs are also obtained.