undefined | Better HN

0 pointsmauricioc0y ago0 comments

For the edge-coloring problem, the optimal number of colors needed to properly color the edges of G is always either Delta(G) (the maximum degree of G) or Delta(G) + 1, but deciding which one is the true optimum is an NP-complete problem.

Nevertheless, you can always properly edge-color a graph with Delta(G) + 1 colors. Finding such a coloring could in principle be slow, though: the original proof that Delta(G) + 1 colors is always doable amounted to a O(e(G) * v(G)) algorithm, where e(G) and v(G) denote the number of edges and vertices of G, respectively. This is polynomial, but nowhere near linear. What the paper in question shows is how, given any graph G, to find an edge coloring using Delta(G) + 1 colors in O(e(G) * log(Delta(G))) time, which is linear time if the maximum degree is a constant.

0 comments

Syzygies0y ago

Yes. The article ran through this point as follows:

"In 1964, a mathematician named Vadim Vizing proved a shocking result: No matter how large a graph is, it’s easy to figure out how many colors you’ll need to color it. Simply look for the maximum number of lines (or edges) connected to a single point (or vertex), and add 1."

I keep wondering why I ever read Quanta Magazine. It takes a pretty generous reading of "need" to make this a correct statement.

JohnKemeny0y ago

Not really. Coloring a graph is almost always talking about proper coloring, meaning that things that objects that are related receive different colors.

If you read the introduction, you'll also read that the goal is to "color each of your lines and require that for every point, no two lines connected to it have the same color."

Ps. "How many colors a graph needs" is a very well established term in computer science and graph theory.

mockerell11mo ago

I think the comment referred to the phrase „a graph needs X (colors or whatever)“. For me, this can be read two ways: 1. „a graph always needs at least X colors“ or 2. „a graph always needs at most X colors“.

Personally, I would interpret this as option 1 (and so did the comment above I assume). In that case, the statement is wrong. But I’d prefer to specify „at most/ at least“ anyways.

Or even better, use actual vocabulary. „For every graph there exists a coloring with X colors.“ or „any graph can be coloured using X colors“.

PS: I also agree with the sentiment about quanta magazine. It’s hard to get some actual information from their articles if you know the topic.

JohnKemeny11mo ago

What about this statement:

No matter how large a car is, it is easy to figure out how much money you'll need to buy it. Simply look at the price tag.

(From: No matter how large a graph is, it’s easy to figure out how many colors you’ll need to color it. Simply look for the maximum ...)

1 more reply

j / k navigate · click thread line to collapse