SFU Discrete Math Seminar: Bojan Mohar

  • Date: 03/15/2022
  • Time: 14:30
Bojan Mohar, SFU

Simon Fraser University


Proper orientations and proper chromatic number


It is an interesting (and not entirely obvious) fact that every graph admits an orientation of its edges so that the outdegrees at vertices form a "coloring" (outdegrees of any two adjacent vertices are different).

The proper chromatic 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 chromatic number are resolved. First it is shown, that $\Vec{\chi}(G)$ of any planar graph $G$ is bounded (in fact, it 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 Yaobin Chen and Hehui Wu.

Other Information: 

Tuesday, March 15th, from 2:30-3:20pm, in K9509*


Zoom option available. Please email the organizers here.