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.