A characterization on orientations of graphs avoiding given lists on out-degrees
主 讲 人 :鲁红亮 教授
活动时间:01月26日10时00分
地 点 :腾讯会议号 8121821941 密码812182
讲座内容:
Let $G$ be a graph and $F:V(G)\to2^N$ be a set function. The graph $G$ is said to be \emph{F-avoiding} if there exists an orientation $O$ of $G$ such that $d^+_O(v)\notin F(v)$ for every $v\in V(G)$, where $d^+_O(v)$ denotes the out-degree of $v$ in the directed graph $G$ with respect to $O$. In this talk, we give a Tutte-type good characterization to decide the $F$-avoiding problem when for every $v\in V(G)$, $|F(v)|\leq \frac{1}{2}(d_G(v)+1)$ and $F(v)$ contains no two consecutive integers. Our proof also gives a simple polynomial algorithm to find a desired orientation. As a corollary, we prove the following result: if for every $v\in V(G)$, $|F(v)|\leq \frac{1}{2}(d_G(v)+1)$ and $F(v)$ contains no two consecutive integers, then $G$ is $F$-avoiding. This partly answers a problem proposed by Akbari et. al. (2020).
主讲人介绍:
鲁红亮,2010博士毕业于南开大学,现任西安交通大学数学院教授,博士生导师,曾受邀于第九届全国组合数学与图论大会做一小时大会报告,2020年荣获“陕西省青年科技奖”。主要研究图的度约束因子与超图的匹配问题,解决了多个图因子及匹配研究领域的公开问题及猜想;已发表及接受发表论文六十余篇,多篇论文发表在Sci. China Math.、SIAM DM、JGT、JCTA、JCTB、EJC等图论领域权威期刊上;共主持四项国家自然科学基金项目,其中三个面上项目,一个青年项目。