# zbMATH — the first resource for mathematics

Gallai and anti-Gallai graphs of a graph. (English) Zbl 1174.05116
Summary: 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.

##### MSC:
 05C99 Graph theory
##### Keywords:
Gallai graphs; anti-Gallai graphs; cographs
Full Text: