KAIST Discrete Math Seminar

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).

An r-dynamic proper k-coloring of a graph G is a proper k-coloring of G such that every vertex in V(G) has neighbors in at least different color classes. The r-dynamic chromatic number of a graph G, written , is the least k such that G has such a coloring. By a greedy coloring algorithm, and the equality holds if and only if G is r-regular with diameter 2 and girth 5. We improve the bound to when . In terms of the chromatic number, we prove when G is k-regular with and show that may exceed when k=r. We prove when G has diameter 2, with equality only for complete bipartite graphs and the 5-cycle. Also, when G has diameter 3, which is sharp. This is joint work with Sogol Jahanbekam, Suil O, and Douglas B. West.