Date: | March 1, 2023 |

Speaker: | Joshua Schroeder, Guest from Georgia Tech |

Time: | 12:15PM |

Place: | Graduate Student Lounge, 7th Floor, Hill Center (and Zoom) |

Link: | Zoom Link You can e-mail the organizer for the password. |

Title: | On the 3-colorability of fork-free and triangle-free graphs |

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 deployedto manage the case analysis.
Therefore thetalk will include a high level description of the code and its role in the proof. |