Session Time & Room : 4E (Aug.24, 17:40-19:20) @A617
Type : Proposal of Minisymposium
Abstract : Graph coloring are fundamental objects of study in graph theory and have many applications including thetheoritical computer scinence, scheduling problems, and mobile phone network problems.
Beginning with the four color theorem, many conjectures and extensions of graph coloring have been proposed.
In addition, relationships with other subjects of graph theory have also been discovered.
However, despite the efforts of many mathematicians, there are still many unsolved problems in graph coloring.
In this mini-symposium, we will explore the latest topics and results concerning coloring conjectures, extensions, and relationships with other subjects.
[02669] Flows and coloring of triangle-free graphs on surfaces
Format : Talk at Waseda University
Author(s) :
Zdeněk Dvořák (Charles University)
Abstract : The near-quadrangulations of surfaces, i.e., graphs where almost all faces have length four, play an important role in the theory of 3-colorability of triangle-free graphs on surfaces. We present a powerful approach to coloring near-quadrangulations using nowhere-zero flows and explore its applications. In particular, we show a connection between the maximum edgewidth of triangle-free non-3-colorable graphs on a given surface and a long-standing conjecture concerning the maximum width of polytopes containing no integer points.
[02782] Alon-Tarsi number of planar graphs
Format : Online Talk on Zoom
Author(s) :
Xuding Zhu (Zhejiang Normal University)
Yangyan Gu (Zhejiang Normal University)
Abstract : This talk presents a simple proof of the result that planar graphs have Alon-Tarsi number at most 5, and that each planar graph $G$ has a matching $M$ such that $G-M$ has Alon-Tarsi number at most 4. The former result is a strengthening of Thomassen’s result that planar graphs are 5-choosable, and the latter result implies that every planar graph $G$ has a matching $M$ such that $G-M$ is online 4-choosable, which is a generalization of Cushing-Kierstead’s result that planar graphs are 1-defective 4-choosable.
[02488] Edge-colourings, hamiltonian cycles, and a problem of Kotzig
Format : Online Talk on Zoom
Author(s) :
Carol T. Zamfirescu (Ghent University)
Abstract : This talk concerns proper edge-colourings of regular graphs in which certain colour pairs form hamiltonian cycles -- such a pair is called perfect. We present a theorem solving Kotzig's problem asking whether planar 5-regular graphs exist admitting an edge-colouring in which all ten pairs are perfect. If time permits, we shall also discuss certain edge-colouring enumeration problems. This talk is based on joint work with Nico Van Cleemput.
[03108] Coloring Graphs with Forbidden Minors
Format : Online Talk on Zoom
Author(s) :
Zi-Xia Song (University of Central Florida)
Michael Lafferty (University of Central Florida)
Abstract : Hadwiger's Conjecture from 1943 states that every graph with no $K_{t}$ minor is $(t-1)$-colorable; it remains open for all $t\ge 7$. Jakobsen in 1971 proved that every graph with no $\mathcal{K}_7^{-2}$ minor is $6$-colorable. In this talk, we present our recent work that every graph with no $\mathcal{K}_8^{-4}$ minor is $7$-colorable, and every graph with no $\mathcal{K}_9^{-6}$ minor is $8$-colorable, where $\mathcal{K}_t^{-s}$ denote the family of graphs obtained from $K_t$ by removing $s$ edges.
