Domov > Obvestila > Bojan Mohar: Proper in-orientations of graphs

Bojan Mohar: Proper in-orientations of graphs

Datum objave: 18. 4. 2016
Vir: Seminar za teorijo grafov in algoritme
Č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.