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.

  • $\begingroup$ 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? $\endgroup$ – EGME Nov 15 '19 at 21:22
  • $\begingroup$ @EGME According to Wikipedia this is possible: en.wikipedia.org/wiki/Overfull_graph $\endgroup$ – joro Nov 16 '19 at 7:30
  • $\begingroup$ 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? $\endgroup$ – EGME Nov 16 '19 at 8:55
  • $\begingroup$ @EGME According to wikipedia G is class 2 iff it has overfull subgraph of maximum degree. $\endgroup$ – joro Nov 16 '19 at 9:29
  • $\begingroup$ 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? $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ Thanks. Isn't this counterexample to the Overfull conjecture? $\endgroup$ – joro Nov 16 '19 at 10:34
  • $\begingroup$ @joro Not unless you find a subgraph in the example which is overfull and has max degree as in the example ... I couldn’t find it ... given who has worked on this problem and found no counterexample, I would rather believe that this simple example is not going to be a counterexample ... (but anyway, I did check, although my visual checks are prone to error). $\endgroup$ – EGME Nov 16 '19 at 10:38
  • $\begingroup$ @joro Also, this misconception I found in your other posts ... put a note there to amend this :) $\endgroup$ – EGME Nov 16 '19 at 10:39
  • $\begingroup$ OK, I added links on cstheory to here. $\endgroup$ – joro Nov 16 '19 at 10:45
  • $\begingroup$ @joro You have a nice problem to work on ... show that finding overfull subgraphs in graphs of large degree is NP-hard ... that is my bet ... $\endgroup$ – EGME Nov 16 '19 at 10:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.