Proper orientations of planar bipartite graphs (Q1684937): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2963514883 / rank | |||
Normal rank |
Revision as of 21:57, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Proper orientations of planar bipartite graphs |
scientific article |
Statements
Proper orientations of planar bipartite graphs (English)
0 references
12 December 2017
0 references
An orientation of a graph is proper if any two adjacent vertices have different indegrees. The proper orientation number of a graph is the minimum of the maximum indegrees taken over all its proper orientations. It is an open question whether the class of planar bipartite graphs has a bounded orientation number. The authors begin with a new and useful result that yields a polynomial-time algorithm to properly orient a connected bipartite graph, and to do so when controlling only the orientation of a spanning tree and the edges incident with one of its leaves. This algorithm produces a proper orientation with indegree at most 6 for a 3-connected planar bipartite graph, and with indegree at most 4 for a tree. (The later bound was known but the proof was not constructive.) By modifying their general construction, they show the proper orientation number of a 3-connected planar bipartite graph is at most 5.
0 references
proper orientation number
0 references
planar graphs
0 references
bipartite graphs
0 references
coloring
0 references