Discrete Math Seminar: Dennis Epple

Abstract:

A $(k,l)$-colouring of a graph is a partition of its vertex set into $k$ independent sets and $l$ cliques. The bichromatic number $\\chi^b$ of a graph is theminimum $r$, such that the graph is $(k,l)$-colourable for all $k+l=r$.The bichromatic number is related to the well-known cochromatic number, which can also be defined in
terms of $(k,l)$-colourings.
The bichromatic number is a fairly recent graph parameter, that arises in the study ofextremal graphs related to a classical result of Erd\\H{o}s, Stone and Simonovits and in the study of the edit distance of graphs from hereditary graph classes. While the cochromatic number has been extensively studied in the literature, there are only few
known structural results for the bichromatic number.
The focus of this talk is to present some foundational results about the bichromatic number, relating it to other graph parametersand investigating extremal cases.