Seminar Details
On the 3-Colorability of Fork-Free and Triangle-Free Graphs
- Start Date: March 1, 2023
- Event Start Time: 12:15 PM
- Event End Time: 1:15 PM
- Seminar Series: Graduate Combinatorics Seminar
- Presenter(s): Joshua Schroeder - Georgia Institute of Technology
- Event Location: Mathematics Graduate Student Lounge -- 7th Floor | Rutgers University | Hill Center | Mathematics Department
- Event Additional Info: <p>See: <a href="https://sites.math.rutgers.edu/~kmg326/GCS/GCS.html">https://sites.math.rutgers.edu/~kmg326/GCS/GCS.html</a></p>
- Presentation Type: Stand Alone Presentation
- 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.