Special Session on Graph Theory

April 24, Saturday, 4:30M-6:30PM

**Room 103**, Building W10 (백마교양교육관), Choongnam National University (충남대학교), Daejeon

## Speakers

- Young Soo Kwon (권영수), Yeungnam University
- Mark H. Siggers, Kyungpook National University
- Jack Koolen, POSTECH
- Tommy Jensen, Kyungpook National University

## Organizers

- Sang-il Oum (엄상일), KAIST
- Seog-Jin Kim (김석진), Konkuk University

## Abstracts

### Classification of nonorientable regular embeddings of Hamming graphs

### Young Soo Kwon (권영수), Yeungnam University

In this talk, the classification of nonorientable regular embeddings of Hamming graph will be considered. The classification shows that there exists a nonorientable regular embedding of Hamming graph H(n,d) if and only if (n=2 and d=2) or (n=3,4) or (n=6 and d=1 or 2) . This is a joint wok with Gareth A. Jones.

### Asymmetric Highly Ramsey Infinite Graphs

### Mark H. Siggers, Kyungpook National University

A graph G is ramsey for a pair of graphs (B,R) if any two-colouring (with blue and red) of the edges yields a blue copy of B or a red copy of R. A pair (B,R) is ramsey infinite if there are an infinite class of graphs that are edge-critical with respect to being ramsey for (B,R).

We talk about several results classifying which pairs are ramsey infinite, and a recent result showing that if B and R are odd-cycles, then not only is (B,R) ramsey-infinite, but there are 2^{O(n^2)} non-isomorphic graphs on n vertices that are edge-critical with respect to being ramsey for (B,R).

### A Moore bound for irregular graphs?

### Jack Koolen, POSTECH

A k-regular graph with diameter D can have at most 1 + k + k(k-1) + …+ k(k-1)^{D-1} vertices. This is known as the Moore bound. In this talk I discuss several versions of this bound for irregular graphs.

### Splitting a Graph by a Circuit

### Tommy R. Jensen, Kyungpook National Unversity

We try to identify a property of circuits in (nonplanar) graphs resembling the separation property of circuits in planar graphs that is derived from the Jordan Curve Theorem. We observe that a conjectured such property implies a strong form of a version of Seymour’s Cycle Double Cover Conjecture due to Luis Goddyn. Our main result proves that the suggested property holds for Hamilton circuits in cubic graphs.