SFU Discrete Math Seminar: Zdenek Dvorak

  • Date: 04/05/2022
  • Time: 14:30
Lecturer(s):
Zdenek Dvorak (Charles University, Prague)
Location: 

Simon Fraser University

Topic: 

3-coloring near-quadrangulations of the plane and the torus using flows

Description: 

A graph drawn in a surface is a k-near-quadrangulation if the product of the lengths of its faces, except for 4-faces, is at most k.
Near-quadrangulations play a fundamental role in the theory of 3-colorability of triangle-free graphs on surfaces. We show how the well-known duality between colorings and flows can be used to design

 

(1) a 3-precoloring extension algorithm for k-near-quadrangulations of the plane, and

(2) a 3-coloring algorithm for k-near-quadrangulations of the torus,

 

with time complexity polynomial in k and the number of vertices.

This is joint work with C. Bang, E. Heath, and B. Lidicky.

Other Information: 

Time: 2:30pm Pacific

Location: Roopm K9509, in-person.