Joshua Schroeder, Georgia Institute of Technology

Abstract

A graph G is said to satisfy the Vizing bound if χ(G)≤ω(G)+1, where χ(G) and ω(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 K1,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.

See: https://sites.math.rutgers.edu/~kmg326/GCS/GCS.html