Bojan Mohar: Proper in-orientations of graphs

 Povzetek. 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.

Predavanje je v okviru Seminarja za teorijo grafov in algoritme.