Skip to main content
MathOverflow

Return to Question

added 73 characters in body
Source Link
vidyarthi
vidyarthi
  • 2.1k
  • 1
  • 16
  • 22

We know that the decision problem of classifying the graphs as class $1$ or class $2$ (with respect to edge coloring) is NP-complete. But, suppose we have to prove a graph to be in class $1$. Does it always imply that we have to find a polynomial time algorithm for the edge coloring of that graph? Like, is it possible to prove a graph to be in class $1$ without describing an explicit algorithm to do so, like, say by computing the Lovasz number of the line graph of the graph?

Most of the problems I have seen invariably lead me to think that one could prove the graph is in class $1$ iff there is a polynomial time algorithm to color the edges of the graph. Is this right? Thanks beforehand.

We know that the decision problem of classifying the graphs as class $1$ or class $2$ (with respect to edge coloring) is NP-complete. But, suppose we have to prove a graph to be in class $1$. Does it always imply that we have to find a polynomial time algorithm for the edge coloring of that graph? Like, is it possible to prove a graph to be in class $1$ without describing an explicit algorithm to do so?

Most of the problems I have seen invariably lead me to think that one could prove the graph is in class $1$ iff there is a polynomial time algorithm to color the edges of the graph. Is this right? Thanks beforehand.

We know that the decision problem of classifying the graphs as class $1$ or class $2$ (with respect to edge coloring) is NP-complete. But, suppose we have to prove a graph to be in class $1$. Does it always imply that we have to find a polynomial time algorithm for the edge coloring of that graph? Like, is it possible to prove a graph to be in class $1$ without describing an explicit algorithm to do so, like, say by computing the Lovasz number of the line graph of the graph?

Most of the problems I have seen invariably lead me to think that one could prove the graph is in class $1$ iff there is a polynomial time algorithm to color the edges of the graph. Is this right? Thanks beforehand.

removed capitals from title
Link
YCor
YCor
  • 63.9k
  • 5
  • 187
  • 285

Complexity of Edge Coloringedge coloring of class 1 graphs

Source Link
vidyarthi
vidyarthi
  • 2.1k
  • 1
  • 16
  • 22

Complexity of Edge Coloring of class 1 graphs

We know that the decision problem of classifying the graphs as class $1$ or class $2$ (with respect to edge coloring) is NP-complete. But, suppose we have to prove a graph to be in class $1$. Does it always imply that we have to find a polynomial time algorithm for the edge coloring of that graph? Like, is it possible to prove a graph to be in class $1$ without describing an explicit algorithm to do so?

Most of the problems I have seen invariably lead me to think that one could prove the graph is in class $1$ iff there is a polynomial time algorithm to color the edges of the graph. Is this right? Thanks beforehand.