Online Event: Open Problem Session (Dec 14)

Another successful open problem session! 🙂 Thank you to everyone who attended and a special thank you to our presenters. The slides are posted below.

Date: Tuesday, December 14
Time: 1:30-4:00pm EST (6:30-9:00pm GMT, 7:30-10:00am Wed NZDT)

Schedule:
Session 1: 1:30-2:30pm EST
Session 2: 3:00-4:00pm EST
Social Time: 4:00pm EST – ??

Format:
In each session, several open problems will be presented. For each problem, we’ll have ~5 minutes for the presentation followed by ~5 minutes for discussion. There may be time at the end of each session for more discussion or unplanned open problem contributions.

Session 1:
1. Nathan Bowler – slides
2. Rose McCarty – slides
3. James Davies – slides
4. Michał Pilipczuk – slides
5. Nicholas Anderson – slides
6. Ben Moore – slides

Session 2:
1. Bruce Richter – slides
2. Michael Wigal – slides
3. Dillon Mayhew – slides
4. Zach Walsh – slides
5. Jorn van der Pol – slides
6. Jim Geelen – slides

Online Talk: Michael Wigal

Tuesday, Dec 7, 3pm ET (8pm GMT, 9am Wed NZDT)
Michael Wigal, Georgia Tech
Approximating TSP walks in subcubic graphs

 
Abstract:
We will show that if $G$ is a $2$-connected simple subcubic graph on $n$ vertices with $n_2$ vertices of degree $2$, then $G$ has a TSP walk of length at most $5n/4 + n_2/4 -1$, establishing a conjecture of Dvořák, Kráľ, and Mohar. This upper bound is best possible. In particular, there are infinitely many subcubic (respectively, cubic) graphs whose minimum TSP walks have length $5n/4 + n_2/4 -1$ (respectively, $5n/4 – 2$). Our proof implies a quadratic-time algorithm for finding such a TSP walk, thereby giving a $5/4$ approximation algorithm for the graphic TSP on simple cubic graphs and improving on the previously best known approximation ratio of $9/7$.

Joint work with Youngho Yoo and Xingxing Yu.

Open Problem Session – Dec 14

The organizers of the Graphs and Matroids Seminar would like to invite you to participate in our Open Problem Session!

The session will take place on Tuesday, December 14 from 1:30 to 4:00pm EST with social time afterwards on Gather Town. For each problem, we’ll have ~5 minutes for the presentation followed by ~5 minutes for discussion. We’re planning to have two sessions of about an hour each with a break in between.

Call for presenters: If you would like to present an open problem, please email Shayla (shaylaredlin at gmail dot com) and let us know if you would prefer presenting in the first hour or the last hour of the session. Please email by Friday, Dec 10.

More details about the schedule and how to attend will be posted closer to Dec 14.

 – Jim, Peter, and Shayla