KAIST Discrete Math Seminar

Given two graphs G and H, the categorical product has vertex set , and two vertices (x,y) and (x’,y’) are adjacent if and . The famous Hedetniemi-Lovász Conjecture asserts that teh chromatic number of equals the minimum of and . In this talk, I will sketch a proof of the fractional version of the conjecture, which says that the fractional chromatic number of equals to the minimum of the fractional chromatic numbers of G and H. This result is then used to prove a conjecture of Burr-Erdős-Lovász on the chromatic Ramsey number of graphs.

Vertex colouring of graphs is an active research area in graph theory. It has wide applications to practical problems and also has many theoretically deep results and challenging problems. Circular colouring of graphs is a refinement of the conventional vertex colouring of graphs. It has atttract a lot of attention in the past twenty years, and becomes an important branch of chromatic graph theory, with many exciting results and new techniques. This talk gives a survey on research in this area.

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.

One version of Kakeya’s problem asks for the smallest convex garden in which a ladder of length one can be rotated fully. The answer to this question was shown to be the equilateral triangle of height one by Pal in 1920.</p>

We consider the following generalization: Given a (not necessarily finite) family F of line segments in the plane, what is the smallest convex figure K such that every segment in F can be translated to lie in K?

We show that as in the classic case, the answer can always be chosen to be a triangle. We also give an O(n log n) time algorithm to compute such an optimal triangle if F consists of n line segments.

Joint work with Sang Won Bae, Hee-Kap Ahn, Joachim Gudmundsson, Takeshi Tokuyama, and Antoine Vigneron.

An L(j,k) labeling of a graph is a vertex labeling such that the difference of the labels of any two adjacent vertices is at least j and that of any two vertices of distance 2 is at least k. The minimum of the spans of all L(j,k)-labelings of G is denoted by . Recently Haque and Jha proved if G is a direct product of complete graphs, then coincide with the trivial lower bound $(N-1)k$ where N is the order of G when j/k is within a certain bound.</p>

In this paper, we suggest a new labeling method of such a graph G. With this method, we extend the range of j/k such that holds. Moreover, we obtain an upper bound of for the remaining cases.