报告题目：Strong list-coloring of clique-hypergraphs of $K_{5}$-minor-free graphs

报告简介：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.

报告人：梁作松，上海大学博士学位， 主要从事组合最优化与图论研究。在国际核心期刊《Journal of Combinatorial Optimization》《Operations Research Letters》《European Journal of Combinatorics》《 Discrete Math》等发表论文20余篇。主持国家自然科学基金2项、省部级项目2项。

报告时间：2021年7月24日（星期六）下午 2:00-3:00.

报告地点：腾讯会议，ID：802 979 938

主办单位：扬州大学数学科学学院

欢迎广大师生参加！