2023-07-28 |
10:30-11:30 |
2023-07-28,10:30-11:30 | LR11 (A7 2F) |
07-28 Morning Math Lecture Room 11 (A7 2F)
|
Speaker |
Orientations of graphs with forbidden out-degree lists Let $G$ be a graph and $F: V(G)\mapsto 2^\mathbb{N}$ be a mapping. The graph $G$ is said to be $F$- avoidable if there exists an orientation $D$ of $G$ such that for each vertex $v$, the out-degree $d^+_D(v)\not\in F(v)$. It was conjectured by Akbari, Dalirrooyfard, Ehsani,Ozeki and Sherkati that if $|F(v)|\le (d(v)-1)/2$ for each vertex $v$, then $G$ is $F$-avoiding , and they showed that $|F(v)|\le d(v)/4$ suffices. By using Combinatorial Nullestellensatz theorem, we improve the bound to $|F(v)|\le [d(v)/3]$. Furthermore, if the maximum degree is sub-exponentail of the minimum degree $\delta$, then if $|F(v)|\le (\sqrt{2}-1-o(1))d(v)\approx (0.41+o(1))d(v)$ for each vertex $v$, then $G$ is $F$-avaidable. This is joint work with Peter Bradshaw, Bojan Mohar in Simon Fraser University, and my students Yaobin Chen, Hao Ma in Fudan University.
|