报告题目：Rainbow independent sets in graphs with maximum degree two

报 告 人：侯新民副教授（中国科学技术大学）

报告时间：2021年12月23日9：30-12：00

报告地点：腾讯会议 923 268 754

报告摘要：

Given a graph $G$, let $f_{G}(n,m)$ be the minimal number $k$ such that every $k$ independent $n$-sets in $G$ have a rainbow $m$-set. Let $\mathcal{D}(2)$ be the family of all graphs with maximum degree at most two. Aharoni et al. (2019) conjectured that (i) $f_G(n,n-1)=n-1$ for all graphs $G\in\mathcal{D}(2)$ and (ii) $f_{C_t}(n,n)=n$ for $t\ge 2n+1$. Lv and Lu (2020) showed that the conjecture (ii) holds when $t=2n+1$. In this talk, we show that the conjecture (ii) holds for $t\ge\frac{1}{3}n^2+\frac{44}{9}n$. Let $C_t$ be a cycle of length $t$ with vertices being arranged in a clockwise order. An ordered set $I=(a_1,a_2,\ldots,a_n)$ on $C_t$ is called a $2$-jump independent $n$-set of $C_t$ if $a_{i+1}-a_i=2\pmod{t}$ for any $1\le i\le n-1$. We also show that a collection of 2-jump independent $n$-sets $\mathcal{F}$ of $C_t$ with $|\mathcal{F}|=n$ admits a rainbow independent $n$-set, i.e. (ii) holds if we restrict $\mathcal{F}$ on the family of 2-jump independent $n$-sets. Moreover, we prove that if the conjecture (ii) holds, then (i) holds for all graphs $G\in\mathcal{D}(2)$ with $c_e(G)\le 4$, where $c_e(G)$ is the number of components of $G$ isomorphic to cycles of even lengths. (This is a joint work with Yue Ma, d Jun Gao, Boyuan Liu, and Zhi Yin).

报告人简介：

侯新民，中国科学技术大学数学科学公司，副教授，博士生导师。感兴趣研究领域包括结构图论、极值图论、组合优化等，已发表学术论文50余篇，主持完成国家自然科学基金4项，省部级项目2项。