# KPPY 97

Sebastian Wiederrecht, Hyemin Kwon, WonTae Hwang, Sunyo Moon, Yanquan Feng

Saturday Oct 07, 2023. 11am - 5:30pm at KNU

Schedule | ||

11:00am - 11:50 |
Yanquan Feng Beijing Jiaotong University | Graphical semiregular representation of finite groups |

12pm - 1:25 | Lunch | |

1:30 - 2:20 |
WonTae Hwang Chonbuk University | An introduction to the zero-divisor graph of rings (with emphasis on matrix rings) |

2:30 - 3:20 |
Sebastian Wiederrecht IBS | Delineating half-integrality of the Erdős-Pósa property for minors |

3:30 - 4:20 |
Hyemin Kwon Ajou University | Odd coloring and strong odd coloring |

4:30 - 5:20 |
Sunyo Moon KIAS | On the Laplacian spectrum of $k$-symmetric graphs |

## Abstracts

Yanquan Feng

Graphical semiregular representation of finite groups

Graphical semiregular representation of finite groups

A digraph or a graph $\Gamma$ is called a digraphical or graphical regular representation (DRR or GRR for short) of a group $G$ respectively, if
${\rm Aut}(\Gamma) \cong G$ is regular on the vertex set $V(\Gamma)$. A group $G$ is called a DRR group or a GRR group if there is a digraph or a graph $\Gamma$ such that $\Gamma$ is a DRR or GRR of $G$. Babai and Godsil classiﬁed
ﬁnite DRR groups and GRR groups in 1980 and 1981, respectively. Then a lot of
variants relative to DRR or GRR, with some restrictions on (di)graphs or groups,
were investigated by many researchers. We extend regular representation to semiregular representation. For a positive integer $m$, a group $G$ is called a DmSR group or a GmSR group, if there is a digraphical or graphical $m$-semiregular representation of $G$, that is, a regular digraph or a graph $\Gamma$ such that ${\rm Aut}(\Gamma) \cong G$ is semiregular on $V(\Gamma)$ with $m$ orbits. Clearly, D1SR and G1SR groups are the DRR and GRR groups. In this talk, we review some progress on DmSR groups and GmSR groups for all positive integer $m$, and their variants by restricting (di)graphs or groups.

WonTae Hwang

An introduction to the zero-divisor graph of rings (with emphasis on matrix rings)

An introduction to the zero-divisor graph of rings (with emphasis on matrix rings)

In this talk, we introduce the notion of the zero-divisor graph which relates the graph
theory to ring theory, and give a survey on the known results on the zero-divisor graphs of
commutative rings and/or matrix rings over fields. If time permits, we would also like to briefly
introduce a work in progress with Ei Thu Thu Kyaw on the structure of the certain subgraphs of the
zero-divisor graph of $2\times 2$ matrix rings over small number rings, which involve a bit of algebraic
geometry and algebraic number theory.

Sebastian Wiederrecht

Delineating half-integrality of the Erdős-Pósa property for minors

Delineating half-integrality of the Erdős-Pósa property for minors

In 1986 Robertson and Seymour proved a generalization of the seminal result of Erdős and Pósa on the duality of packing and covering cycles:
A graph has the Erdős-Pósa property for minors if and only if it is planar.
In particular, for every non-planar graph $H$ they gave examples showing that the Erdős-Pósa property does not hold for $H$.
Recently, Liu confirmed a conjecture of Thomas and showed that every graph has the half-integral Erdős-Pósa property for minors.
In this paper we start the delineation of the half-integrality of the Erdős-Pósa property for minors.

We conjecture that for every graph $H$ there exists a finite family $\mathfrak{F}_H$ of parametric graphs such that $H$ has the Erdős-Pósa property in a minor-closed graph class $\mathcal{G}$ if and only if $\mathcal{G}$ excludes a minor of each of the parametric graphs in $\mathfrak{F}_H$. We prove this conjecture for the class $\mathcal{H}$ of Kuratowski-connected shallow-vortex minors by showing that, for every non-planar $H\in\mathcal{H}$ the family $\mathfrak{F}_H$ can be chosen to be precisely the two families of Robertson-Seymour counterexamples to the Erdős-Pósa property of $H$. This is joint work with Christophe Paul, Evangelos Protopapas, and Dimitrios Thilikos.

We conjecture that for every graph $H$ there exists a finite family $\mathfrak{F}_H$ of parametric graphs such that $H$ has the Erdős-Pósa property in a minor-closed graph class $\mathcal{G}$ if and only if $\mathcal{G}$ excludes a minor of each of the parametric graphs in $\mathfrak{F}_H$. We prove this conjecture for the class $\mathcal{H}$ of Kuratowski-connected shallow-vortex minors by showing that, for every non-planar $H\in\mathcal{H}$ the family $\mathfrak{F}_H$ can be chosen to be precisely the two families of Robertson-Seymour counterexamples to the Erdős-Pósa property of $H$. This is joint work with Christophe Paul, Evangelos Protopapas, and Dimitrios Thilikos.

Hyemin Kwon

Odd coloring and strong odd coloring

Odd coloring and strong odd coloring

Petrševski and Škrekovski introduced an odd coloring of a graph $G$, which is a relaxation of a proper coloring of the square of $G$. An odd $k$-coloring is a proper $k$-coloring such that every non-isolated vertex has a color appearing an odd number of times on its neighborhood. Naturally, we could obtain a strong version of an odd coloring, which is a strong odd coloring: a strong odd $k$-coloring is a proper $k$-coloring such that for every non-isolated vertex, each color on its neighborhood appears an odd number of times. The minimum $k$ for which $G$ has a strong odd $k$-coloring is the strong odd chromatic number of $G$, denoted $\chi_{so}(G)$. We present results on $\chi_{so}(G)$ for a sparse graph $G$ and compare them with the results of an odd coloring of $G$ and a proper coloring of the square of $G$. This talk is based on joint work with Eun-Kyung Cho, Ilkyoo Choi, and Boram Park.

Sunyo Moon

On the Laplacian spectrum of $k$-symmetric graphs

On the Laplacian spectrum of $k$-symmetric graphs

For some positive integer $k$, if the finite cyclic group $Z_k$ can act freely on a graph $G$, then we say that $G$ is $k$-symmetric. In 1985, Faria showed that the multiplicity of Lapla
cian eigenvalue 1 is greater than or equal to the difference between the number of pendant vertices and the number of quasi-pendant vertices. But if a graph has a pendant vertex, then it is a
t most $1$-connected. In this talk, we introduce a class of $2$-connected $k$-symmetric graphs with a Laplacian eigenvalue $1$. We also give a class of $k$-symmetric graphs in which all Lapla
cian eigenvalues are integers. This talk is based on the joint work with Hyungkee Yoo.