# Bojan Mohar: Proper in-orientations of graphs

Date of publication: 18. 4. 2016

Graph theory and algorithms seminar

Četrtek 21. april 2016 ob 12:15 v PS na Jadranski 19.

An orientation of the edges of a graph is proper if indegrees of any two
adjacent vertices are different from each other. A nice argument shows
that every graph admits a proper orientation. Finding proper
orientations such that the maximum indegree is small is NP-hard and
little is known. For example, it has been proved that every tree has a
proper orientation with maximum indegree at most 4 (which is best
possible). A recent new result will be presented.