Vizing's conjecture for cographs

Abstract

We show that if $G$ is a cograph, that is $P_4$-free, then for any graph $H$, $\gamma (G\square H)\ge \gamma (G)\gamma (H)$. By the characterization of cographs as a finite sequence of unions and joins of $K_1$, this result easily follows from that of Bartsalkin and German. However, the techniques used are new and may be useful to prove other results.

6 pages, 2 figures. Since cographs are disjoint unions of graphs with domination numbers one or two, this result is implied by the work of Bartsalkin and German. However, the techniques presented are new and may be useful to other researchers in the field

References in corpus (1)

• A new bound for Vizing's conjecture