Title：Strong list-coloring of clique-hypergraphs of $K_{5}$-minor-free graphs

Abstract：Let $G$ be a connected simple graph with at least one edge. The hypergraph $\mathcal{H}=\mathcal{H}(G)$ with the same vertex set as $G$ whose hyper-edges are the maximal cliques of $G$ is called the clique-hypergraph of $G$. A list-assignment  of $G$ is a function $L$ which assigns to each vertex $v\in V(G)$ a set $L(v)$ (called the list of $v$). A $k$-list-assignment of $G$ is a list-assignment $L$ such that  $L(v)$ has at least $k$ elements for every $v\in V(G)$. For a given list assignment $L$, a list-coloring of  $\mathcal{H}(G) $ is a function $c: V(G)\rightarrow \cup_{v}L(v)$ such that $c(v)\in L(v) $ for every $v\in V(G)$ and no hyper-edge of  $\mathcal{H}(G)$ is monochromatic. A list-coloring of $\mathcal{H}(G)$ is strong  if no $3$-cycle of $G$ is monochromatic.  $\mathcal{H}(G)$ is (strongly) $k$-choosable  if, for every $k$-list assignment $L$, there exists a (strong) list-coloring of  $\mathcal{H}(G)$. Mohar and $\check{S}$krekovski proved that the clique-hypergraphs of planar graphs are strongly $4$-choosable   (Electr. J. Combin. 6 (1999), \#R26). In this paper  we give a short proof  of the result and   present a linear time algorithm for  the strong  list-$4$-coloring of $\mathcal{H}(G)$ if $G$ is a planar graph. In addition, we  prove that $\mathcal{H}(G)$ is  strongly $4$-choosable if $G$ is a $K_{5}$-minor-free graph, which is a  generalization of their  result.

Speaker：Liang Zuosong obtained his Ph. D. from Shanghai University. His research interests include graph theory and Combinatorics. Many of his results published on《Journal of Combinatorial Optimization》《Operations Research Letters》《European Journal of Combinatorics》《 Discrete Math》.

Date：2:00pm-3:00pm 2021-7-24（Saturday）.

Tencent Meeting ID： 802 979 938

Organizer：School of Mathematical Science

Students and teachers who are interested in graph theory are welcome.