KAIST Discrete Math Seminar

Wiring diagrams are widely used combinatorial objects that are mainly used to describe reduced words of a permutation. In this talk, I will mention a fun property I recently found about those diagrams, and then introduce other results and problems related to this property.

The choosability of a graph G is the minimum k such that having k colors available at each vertex guarantees a proper coloring. Given a toroidal graph G, it is known that , and if and only if G contains . Cai, Wang, and Zhu proved that a toroidal graph G without 7-cycles is 6-choosable, and if and only if G contains . They also prove that a toroidal graph G without 6-cycles is 5-choosable, and conjecture that if and only if G contains . We disprove this conjecture by constructing an infinite family of non-4-colorable toroidal graphs with neither nor cycles of length at least 6; moreover, this family of graphs is embeddable on every surface except the plane and the projective plane. Instead, we prove the following slightly weaker statement suggested by Zhu: toroidal graphs containing neither (a missing one edge) nor 6-cycles are 4-choosable. This is sharp in the sense that forbidding only one of the two structures does not ensure that the graph is 4-choosable.

Branch-width and path-width are width parameters of graphs and matroids, which measure how easy it is to decompose a graph or a matroid into a tree-like or path-like structure via separations of small order. These parameters have been used not only for designing efficient algorithms with the inputs of small branch-width or path-width, but also for proving theoretical structural theorems by providing a rough structural description. We will describe a polynomial-time algorithm to construct a path-decomposition or a branch-decomposition of width at most k, if it exists, for a matroid represented over a fixed finite field for fixed k. Our approach is based on the dynamic programming combined with the idea developed by Bodlaender for his work on tree-width of graphs. For path-width, this is a new result. For branch-width, this improves the previous work by Hlineny and Oum (Finding branch-decompositions and rank-decompositions, SIAM J. Comput., 2008) which was very indirect; their algorithm is based on the upper bound on the size of minor obstructions proved by Geelen et al. (Obstructions to branch-decompositions of matroids, JCTB, 2006) and requires testing minors for each of these obstructions. Our new algorithm does not use minor obstructions. As a corollary, for graphs, we obtain an algorithm to construct a rank-decomposition of width at most k if it exists for fixed k. This is a joint work with Jisu Jeong (KAIST) and Eun Jung Kim (CNRS-LAMSADE).