KAIST Discrete Math Seminar

We consider a well-known combinatorial search problem. Suppose that there are n identical looking coins and some of them are counterfeit. The weights of all authentic coins are the same and known a priori. The weights of counterfeit coins vary but different from the weight of an authentic coin. Without loss of generality, we may assume the weight of authentic coins is 0. The problem is to find all counterfeit coins by weighing sets of coins (queries) on a spring scale. Finding the optimal number of queries is difficult even when there are only 2 counterfeit coins.
We introduce a polynomial time randomized algorithm to find all counterfeit coins when the number of them is known to be at most m≥2 and the weight w(c) of each counterfeit coin c satisfies α≤|w(c)|≤β for fixed constants α, β>0. The query complexity of the algorithm is O((m log n)/log m), which is optimal up to a constant factor. The algorithm uses, in part, random walks.
We will also discuss the problem of finding edges of a hidden weighted graph using a certain type of queries.

A path cover of a graph is a set of disjoint paths such that every vertex in the graph appears in one of the paths. We prove an upper bound for the minimum size of a path cover in a connected 4-regular graph with n vertices, confirming a conjecture by Graffiti.pc. We also determine the minimum number of vertices in a connected k-regular graph that is not Hamiltonian, and we solve the analogous problem for Hamiltonian paths.
This is a partly joint work with Gexin Yu and Rui Xu.

A dynamic coloring of a graph G is a proper coloring of the vertex set V(G) such that for each vertex of degree at least 2, its neighbors receive at least two distinct colors. A dynamic k-coloring of a graph is a dynamic coloring with k colors. Note that the gap χ_d(G) – χ(G) could be arbitrarily large for some graphs. An interesting problem is to study which graphs have small values of χ_d(G) – χ(G).
One of the most interesting problems about dynamic chromatic numbers is to find upper bounds of χ_d(G)$ for planar graphs G. Lin and Zhao (2010) and Fan, Lai, and Chen (recently) showed that for every planar graph G, we have χ_d(G)≤5, and it was conjectured that χ_d(G)≤4 if G is a planar graph other than C₅. (Note that χ_d(C₅)=5.)
As a partial answer, Meng, Miao, Su, and Li (2006) showed that the dynamic chromatic number of Pseudo-Halin graphs, which are planar graphs, are at most 4, and Kim and Park (2011) showed that χ_d(G)≤4 if G is a planar graph with girth at least 7.
In this talk we settle the above conjecture that χ_d≤4 if G is a planar graph other than C₅. We also study the corresponding list coloring called a list dynamic coloring.
This is joint work with Seog-Jin Kim and Won-Jin Park.

The well-known Ohba Conjecture says that every graph G with |V(G)|≤ 2χ(G)+1 is chromatic choosable.
This paper studies an on-line version of Ohba Conjecture. We prove that unlike the off-line case, for k≥3, the complete multipartite graph K_{2*(k-1), 3} is not on-line chromatic-choosable. Based on this result, the on-line version of Ohba Conjecture is modified as follows: Every graph G with |V(G)|≥ 2χ(G) is on-line chromatic choosable. We present an explicit strategy to show that for any positive integer k, the graph K_2*k is on-line chromatic-choosable. We then present a minimal function g for which the graph K_{2*(k-1), 3} is on-line g-choosable. This is joint work with Young Soo Kwon, Daphne Der-Fen Liu, and Xuding Zhu.