Seminars & Colloquia Calendar

Title: Abstract: A graph $G$ is said to satisfy the Vizing bound if $\chi(G)\leq \omega(G)+1$,  where $\chi(G)$ and $\omega(G)$ denote  the  chromatic  number  and  clique  number of $G$, respectively. It was conjectured by Randerath in 1998 that if $G$ is a triangle-free and fork-free graph, where the fork (also known as trident) is obtained from $K_{1,4}$ by subdividing two edges, then $G$ satisfies the Vizing bound. This talk will outline the proof of this conjecture. In the verification of the proof, a code package for automatically updating graphs about which we have partial information such as forbidden subgraphs/colorability was developed and deployed to manage the case analysis. Therefore, the talk will include a high level description of the code and its role in the proof.