A characterization on orientations of graphs avoiding given lists on out-degrees

主 讲 人 ：鲁红亮    教授

活动时间：01月26日10时00分    

地      点 ：腾讯会议号 8121821941 密码812182

讲座内容：

Let $G$ be a graphand $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 theout-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等图论领域权威期刊上；共主持四项国家自然科学基金项目，其中三个面上项目，一个青年项目。

发布时间：2024-01-24 20:33:22