SFU Discrete Math Seminar: Bojan Mohar

  • Date: 03/15/2022
  • Time: 14:30
Lecturer(s):
Bojan Mohar, SFU
Location: 

Simon Fraser University

Topic: 

Proper orientations and proper chromatic number

Description: 

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.