# 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.

• Is it clear that the problem of finding a subgraph S of G which is overfull and has Delta(S)=Delta(G) is in P? – EGME Nov 15 '19 at 21:22
• @EGME According to Wikipedia this is possible: en.wikipedia.org/wiki/Overfull_graph – joro Nov 16 '19 at 7:30
• If G has an overfull subgraph S with Delta(G)=Delta(S) then it is class 2, but a G with Delta(G)>=n/3 might not have such a subgraph ... or do you claim the contrary? – EGME Nov 16 '19 at 8:55
• @EGME According to wikipedia G is class 2 iff it has overfull subgraph of maximum degree. – joro Nov 16 '19 at 9:29
• Right, but the question is whether G has such a subgraph ... it is not clear ... it might and it might not ... can you construct an example? – EGME Nov 16 '19 at 9:30

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.