Academy of Mathematics and Systems Science, CAS
Colloquia & Seminars

Speaker:	吴河辉，上海数学中心长聘副教授
Inviter:	交叉中心
Title:	Proper orientations and proper orientation number
Language:	Chinese
Time & Venue:	2022.12.12 15:00-16:00 腾讯会议：682-358-567
Abstract:	?The proper orientation number \Vec{\chi}(G) of a graph G is the minimum k such that there exists an orientation of the edges of G with all vertex-outdegrees at most k and such that for any adjacent vertices, the outdegrees are different. Two major conjectures about the proper orientation number are resolved. First it is shown, that \Vec{\chi}(G) of any planar graph G is at most 14. Secondly, it is shown that for every graph, \Vec{\chi}(G) is at most O(\frac{r\log r}{\log\log r})+\tfrac{1}{2}\MAD(G), where r=\chi(G) is the usual chromatic number of the graph, and \MAD(G) is the maximum average degree taken over all subgraphs of G. Several other related results are derived. Our proofs are based on a novel notion of fractional orientations. This is joint work with Professor Bojan Mohar and my student Yaobin Chen.