KPPY 97

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 classified finite 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.

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.

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.

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.

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.