Due to the equivalence of the 1-coloring numbers with degeneracy, we note that both 1-Orderable and Weak 1-Orderable can be solved in linear time using a greedy algorithm.
Finally, our results make use of the problem 2-Clause 3-SAT, defined below.
Schaefer's dichotomy theorem implies that 2-Clause 3-SAT is NP-complete [1]}.
