Complexity of edge coloring graphs with $\Delta(G) \ge n/3$ assuming the overfull conjecture Closely related to this on cstheory.
Let $G$ be graph of order $n$ with $\Delta(G) \ge n/3$.
Assume the overfull conjecture.
Can we edge color $G$ with minimal number of colors in polynomial time?
The decision problem if $G$ class 2 is polynomial by the overfull conjecture.
Probably some kind of coloring gadget is needed.
 A: As an example of a graph of large degree ($\Delta(G)\geq n/3$) which does not have an overfull subgraph $S$ with $\Delta(S)=\Delta(G)$ consider the graph obtained from two disjoint 6-circuits by identifying them at a vertex, so you get a “figure 8” graph. This graph is clearly of large degree and has no overfull subgraph as is wanted (but it is not easy to check it does not have an overfull subgraphs of large degree ... you need to check all the non-isomorphic subgraphs $S$ with $\Delta(S)=\Delta(G)$ for overfullness ... I suspect that doing that in general is NP-hard).  But in any case, it is easily seen to be class 1.
Concluding, there is a problem with the post, in that the OP seems to assume that a graph $G$ of large degree has an overfull subgraph with max degree as in $G$.  If this were true, then the conjecture would certainly imply that the decision problem concerning the color class of $G$ would be in P, but as it is, there is no such implication in sight.  Also, if it were proven that finding overfull subgraphs with sufficiently large max degree in graphs of large degree is in P, the stated implication would also follow.  However, I suspect it is easier to prove that this is NP-hard.
