KPPY 53

A graph is edge-primitive if its automorphism group acts primitively on edges. In 1973 Weiss [Kantenprimitive Graphen vom Grad drei. J. Combin. Theory Ser. B 15, 269-288 (1973)] determined edge-primitive cubic graphs. In this paper, we classify edge-primitive tetravalent graphs.

We report some results about a product version of the Erdos-Ko-Rado theorem for cross t-intersecting families of subsets (subspaces, and weighted subsets). One of the main tools is a Hoffman's result which bounds the independence number of a given regular graph by using the eigenvalues of the adjacency matrix.

Let $ f_{e}$ (respectively, $ f_{v}$) denote the number of faulty edges (respectively, vertices) in an $ n$-dimensional hypercube $ Q_n$. In this paper, as an extension of a result in [C.H. Tsai, Fault-tolerant cycles embedded in hypercubes with mixed link and node failures, Applied Mathematics Letters 21 (2008) 855-860], we prove that $ Q_{n}$ for $ n\geqslant5$ contains an fault-free cycle of every even length from 4 to $ 2^{n}-2f_{v}$ inclusive if $ f_{e}\leqslant2n-5$ and $ f_{v}+f_{e}\leqslant2n-4$ with every vertex has at least two fault-free edges incident to it.

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. The dynamic chromatic number $ \chi_d(G)$ is the smallest number $ k$ such that there is a dynamic coloring of $ G$ with $ k$ colors. It is known that the gap $ \chi_d (G) - \chi(G)$ could be arbitrarily large for some graphs.

Based on the Four Color Theorem, one of the most interesting problems about dynamic chromatic numbers is to find upper bounds of $ \chi_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 $ \chi_d(G) \leq 5$, which is best possible because $ \chi_d(C_5)=5$. Also, it was conjectured that $ \chi_d(G) \leq 4$ if $ G$ is a planar graph without a $ C_5$ as a component. As a partial answer, Kim and Park (2011) showed that $ \chi_d(G) \leq 4$ if $ G$ is a planar graph with girth at least 7.

In this talk we settle the above conjecture that $ \chi_d(G) \leq 4$ if $ G$ is a planar graph without a $ C_5$ as a component. We also study the corresponding list coloring called a list dynamic coloring. This is joint work with Seog-Jin Kim and Won-Jin Park.

This talk consists of two parts. In the first part, we show that for given $\alpha>2$, there are only finitely many distance-regular graphs with valency $k$, diameter $D\geq3$ and at most $\alpha k$ vertices besides ($D=3$ and the distance-regular graphs are primitive) and ($D=4$ and the distance-regular graphs are antipodal and bipartite). To show this result, we first show that at least one of $a_1$ and $c_2$ is not too small. Also, we used that for $D\geq6$, if the ratio $\frac{b_2}{c_2}$ is bounded, then there are only finitely many such distance-regular graphs. That is, this result is a generalization of earlier work.

It is known that if a distance-regular graph is not antipodal and with valency $k$ and diameter $D\geq3$, then $k\leq k_D(k_D -1)$ and $k_{D-1} > k$. In the second part, we focus on the number $k_{D-1} + k_D$ for a non-antipodal distance-regular graph with diameter $D\geq3$. We first classify the distance-regular graphs with valency $k$, diameter $D=3$ and number of vertices at most $3k+1$. Here note that, in some sense, this result is an intersection of the two parts. Then we use this result to classify the distance-regular graphs with diameter $D$ at least three, valency $k$ and $k_{D-1} + k_D \leq 2k$.

This is joint work with Prof. Jack Koolen at POSTECH.