1
$\begingroup$

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.

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

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Thanks. Isn't this counterexample to the Overfull conjecture? $\endgroup$
    – joro
    Commented Nov 16, 2019 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
    Commented Nov 16, 2019 at 10:38
  • $\begingroup$ @joro Also, this misconception I found in your other posts ... put a note there to amend this :) $\endgroup$
    – EGME
    Commented Nov 16, 2019 at 10:39
  • $\begingroup$ OK, I added links on cstheory to here. $\endgroup$
    – joro
    Commented Nov 16, 2019 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
    Commented Nov 16, 2019 at 10:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .