学术活动

当前位置:首页>>学术交流>>学术活动

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等图论领域权威期刊上;共主持四项国家自然科学基金项目,其中三个面上项目,一个青年项目。