The complexity of the proper orientation number
From MaRDI portal
Publication:2445254
DOI10.1016/j.ipl.2013.07.017zbMath1284.68286arXiv1305.6432OpenAlexW2155184843MaRDI QIDQ2445254
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
computational complexityNP-completenesspolynomial algorithmsvertex coloringgraph orientationproper orientationplanar 3-SAT (type 2)
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