Seminars & Colloquia Calendar

Download as iCal file

Graduate Student Combinatorics Seminar Sponsored by DIMACS

On the 3-colorability of fork-free and triangle-free graphs

Joshua Schroeder

Location:  Graduate Student Lounge, 7th Floor, Hill Center and Zoom
Date & time: Wednesday, 01 March 2023 at 12:15PM - 1:15PM

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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.