Let $C$ be the class of graphs satisfying $\Delta(G) \ge n/3$, where $\Delta(G)$ is the maximum degree of a graph $G$, and $n$ denotes the number of vertices.
- What is the complexity of edge coloring graphs in $C$?
- Is there a reduction from SAT to edge coloring graphs in $C$?
Related to this question. A positive answer means a plausible graph theory conjecture implies $\sf NP=coNP$. A negative answer would greatly surprise me since all graphs of sufficiently large degree will be efficiently edge-colorable.
Possible approach is using some gadget like here
In addition this might help for counterexample for the conjecture (if false).