Vizing's conjecture for cographs

MaRDI QIDQ6277969zbMATH OpenFDO

Authors Elliot Krop

Publication date 27 September 2016

Abstract: We show that if $G$ is a cograph, that is $P_4$-free, then for any graph $H$, $gamma(GsquareH)geqgamma(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.

This page was built for publication: Vizing's conjecture for cographs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6277969)