# KPPY 67

Alexander Stoimenov, Ilkyoo Choi, Semin Oh, Sejeong Bang

Dec 06 2014. 11am-5:00pm at KNU

Schedule | ||

11:00am - 11:50 |
Alexander Stoimenov Gwangju Institute of Science and Technology | On dual triangulations of surfaces (Part II) |

12pm - 1:25 | Lunch | |

1:30 - 2:20 |
Ilkyoo Choi KAIST | Improper coloring of planar graphs |

2:30 - 3:20 |
Semin Oh Pusan National University | Zeta functions of quotients of the integer polynomial ring with rank two |

3:30 - 4:20 |
Sejeong Bang Yeungnam University | A bijection between aperiodic palindromes and connected circulant graphs |

4:30 - 5:20 |
Various | Problem Session |

## Abstracts

Alexander Stoimenov

On dual triangulations of surfaces (Part II)

On dual triangulations of surfaces (Part II)

The goal is to report on some long-term work on certain
combinatorial properties of knot/link diagrams of given
canonical genus. These turned out to have various ramifications
and applications, including (1) enumeration of alternating knots
by genus, (2) words in formal alphabets (Wicks forms), (3) graph
embedding problems on surfaces, (4) markings and the $sl_N$ graph
polynomial, (5) hyperbolic volume of polyhedra, graphs and links.
I will try to explain (at least as far as time allows) some
interrelations between these topics.

Ilkyoo Choi

Improper coloring of planar graphs

Improper coloring of planar graphs

A graph is $(d_1, \ldots, d_r)$-colorable if its vertex set can be partitioned into $r$ sets $V_1, \ldots, V_r$ where the maximum degree of the graph induced by $V_i$ is at most $d_i$ for each $i\in \{1, \ldots r\}$.
For improper coloring of planar graphs with two parts, given $g$ and $d_1$, the question of determining the minimum $d_2=d_2(g, d_1)$ such that planar graphs with girth $g$ are $(d_1, d_2)$-colorable has attracted much interest.
The finiteness of $d_2(g, d_1)$ is known for all cases except when $(g, d_1)=(5, 1)$.
Montassier and Ochem, as well as Rapaud, asked if $d_2(5, 1)$ is finite.
We answer this question in the affirmative with $d_2(5, 1)\leq 10$; namely, we prove that all planar graphs with girth at least $5$ are $(1, 10)$-colorable.
Moreover, we prove that for any Euler genus $\gamma$, there exists a $K=K(\gamma)$ where graphs with girth $5$ that are embeddable on a surface of Euler genus $\gamma$ are $(1, K)$-colorable.
This is joint work with H. Choi, J. Jeong, and G. Suh.

Semin Oh

Zeta functions of quotients of the integer polynomial ring with rank two

Zeta functions of quotients of the integer polynomial ring with rank two

For a ring $R$, the zeta function of $R$ is defined by
\[ \zeta_R(s)=\sum_{I} (R:I)^{-s},\]
the sum extending over all ideals $I$ in $R$ with finite index $(R:I)$. We only view the zeta function as a formal Dirichlet series.
Using fiber product diagrams, we find the zeta functions in the cases
\[R=\mathbb{Z}[x]/((x-a)(x-b)),\]
where $a$ and $b$ are integers. Then we get the zeta functions of adjacency algebras of complete graphs as a corollary.

Sejeong Bang

A bijection between aperiodic palindromes and connected circulant graphs

A bijection between aperiodic palindromes and connected circulant graphs

In this talk, we show that there is a one-to-one correspondence between the set of compositions (resp. prime compositions) of $n$ and the set of circulant digraphs (resp. connected circulant digraphs) of order $n$. We also show that there is a one-to-one correspondence between the set of palindromes (resp. aperiodic palindromes) of $n$ and the set of circulant graphs (resp. connected circulant graphs) of order $n$. As a corollary of this correspondence, we enumerate the number of connected circulant (di)graphs of order $n$.

Various

Problem Session

Problem Session