The complexity of the proper orientation number

DOI10.1016/j.ipl.2013.07.017zbMath1284.68286arXiv1305.6432OpenAlexW2155184843MaRDI QIDQ2445254

Ali Dehghan, Arash Ahadi

Publication date: 14 April 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1305.6432

zbMATH Keywords

computational complexityNP-completenesspolynomial algorithmsvertex coloringgraph orientationproper orientationplanar 3-SAT (type 2)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Related Items (12)

On the proper orientation number of chordal graphs ⋮ Proper orientation of cacti ⋮ Weighted proper orientations of trees and graphs of bounded treewidth ⋮ On the semi-proper orientations of graphs ⋮ Proper 3-orientations of bipartite planar graphs with minimum degree at least 3 ⋮ Is there any polynomial upper bound for the universal labeling of graphs? ⋮ Proper orientations of planar bipartite graphs ⋮ Proper orientations and proper chromatic number ⋮ Proper orientation, proper biorientation and semi-proper orientation numbers of graphs ⋮ On the proper orientation number of bipartite graphs ⋮ On the in-out-proper orientations of graphs ⋮ On the proper arc labeling of directed graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of two graph orientation problems
• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
• Coloring chip configurations on graphs and digraphs
• Vertex-coloring edge-weightings: towards the 1-2-3-conjecture
• Distances in orientations of graphs
• Edge weights and vertex colours
• Minimizing maximum indegree
• Degree constrained subgraphs
• GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
• The NP-Completeness of Edge-Coloring
• NP completeness of finding the chromatic index of regular graphs
• Directed Network Design with Orientation Constraints
• Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures

This page was built for publication: The complexity of the proper orientation number