A 53-Year-Old Network Coloring Conjecture Is Disproved (quantamagazine.org) 49
In just three pages, a Russian mathematician has presented a better way to color certain types of networks than many experts thought possible. From a report:
A paper posted online last month has disproved a 53-year-old conjecture about the best way to assign colors to the nodes of a network. The paper shows, in a mere three pages, that there are better ways to color certain networks than many mathematicians had supposed possible. Network coloring problems, which were inspired by the question of how to color maps so that adjoining countries are different colors, have been a focus of study among mathematicians for nearly 200 years. The goal is to figure out how to color the nodes of some network (or graph, as mathematicians call them) so that no two connected nodes share the same color. Depending on the context, such a coloring can provide an effective way to seat guests at a wedding, schedule factory tasks for different time slots, or even solve a sudoku puzzle.
Graph coloring problems tend to be simple to state, but they are often enormously hard to solve. Even the question that launched the field -- Do four colors suffice to color any map? -- took more than a century to answer (the answer is yes, in case you were wondering). The problem tackled in the new paper seemed, until now, to be no exception to this rule. Unsolved for more than 50 years, it concerns tensor products -- graphs made by combining two different graphs (call them G and H) in a specific way. The tensor product of G and H is a new, larger graph in which each node represents a pair of nodes from the original graphs -- one from G and one from H -- and two nodes in the tensor product are connected if both their corresponding nodes in G and their corresponding nodes in H are connected.
Graph coloring problems tend to be simple to state, but they are often enormously hard to solve. Even the question that launched the field -- Do four colors suffice to color any map? -- took more than a century to answer (the answer is yes, in case you were wondering). The problem tackled in the new paper seemed, until now, to be no exception to this rule. Unsolved for more than 50 years, it concerns tensor products -- graphs made by combining two different graphs (call them G and H) in a specific way. The tensor product of G and H is a new, larger graph in which each node represents a pair of nodes from the original graphs -- one from G and one from H -- and two nodes in the tensor product are connected if both their corresponding nodes in G and their corresponding nodes in H are connected.
Why not just use six or seven colors... (Score:4, Funny)
Re:Why not just use six or seven colors... (Score:5, Informative)
Re:Why not just use six or seven colors... (Score:5, Funny)
But I got, like, 64 different crayons for $5.00. There are even bigger boxes. That's not even close to scarce.
Re: (Score:2)
Re: (Score:1)
Truth. As a colorblind data manager, this always comes up, especially since certain default schemes (Office) can cause headaches. Then there is the added dimension of what type of colorblindness. So yeah, five tends to be a sane limit without running into a certain type of colorblindness.
Re:Why not just use six or seven colors... (Score:4, Informative)
Stated another way, if you know the minimum and maximum you can feel comfortable knowing that any value you choose in that range is acceptable, particularly when the value you choose may subject other parts of the design to constraints. It's about laying a solid foundation to build on.
Also, I don't think they disproved the 4-color statement in this article. They disproved a derivative theory about multiple subgraph minimum coloring being equal to the smaller of the minimum colors of the two subgraphs, specifically a formula was made to specifically find those counter-examples.
The problem with this field of math (discrete math) is sometimes the proofs are pretty abstracted from the problems they seek to solve, and they can be unconvincing.
Re:Why not just use six or seven colors... (Score:5, Insightful)
Re: (Score:2)
The informative answer already present in the TFS wasn't ruined by it, but you wouldn't take that one either.
"The goal is to figure out how to color the nodes of some network (or graph, as mathematicians call them) so that no two connected nodes share the same color. Depending on the context, such a coloring can provide an effective way to seat guests at a wedding, schedule factory t
Re: (Score:3)
That depends on your application.
I do coloring on graphs to build parallel execution schedules of standard graph algorithms. In that case whether I have 12 colors or 15 is not a big deal; it adds a bit of synchronization, but fundamentally not a problem. So we use greedy coloring heuristics there. Coloring time is actually almost more important than the quality of the coloring.
Graph coloring can also be used to determine how to schedule communications in a complex ad hoc wireless mesh network. So each color
Re: (Score:1)
This is tantamount to "Why care about pure math?". Because we don't know the applications yet. You're on a computer. Using bases other than 10, proving theorems in Boolean logic, that kind of stuff was all done as "pure math" before anybody had a practical computer. When applications were found, the theory was ready and waiting.
Ha Ha (Score:2)
Why not just use six or seven colors...
Great, now you have 200 things in a graph, how do you color them so no colors touch - can you? You've run into the same problem.
Or you can say I'll use as many colors as there are network elements but then the question is do you have enough display fidelity to distinguish the two slightly different shades of blue next to each other, and eventually the fidelity of the human eye to resolve color differences.
If you are just talking about color of course, since the real p
Re: (Score:2)
You see mathematicians with a colouring book.
Mathematicians see optimal answers to a small problem space that is a tiny part of a huge overall problems space which solves problems which people are desperately crying out for solutions for, or even just to resolve an upper/lower bound so that they can be sure they always have enough resources to solve the problem when run as a tiny part of an entire body of equations across months of supercomputer time to resolve completely unrelated problems.
All those people
Re: (Score:2)
It's quite literally like saying "Why bother to make a bit of screws in 58mm as well as 100mm lengths? Can't you just use one for everything?".
One size of screws would greatly simplify IKEA furniture. Instead of having to count out 3 of size A, 7 of size B, 5 of size C and 5 of size D . . . you would just need to count if you had 20 screws. And you wouldn't need to worry about putting in a size A in a size B hole, where the difference is barely distinguishable.
Re: (Score:1)
Re: (Score:2)
There are some software algorithms that are based on colouring graphs.
E.g. red/black-trees. https://en.wikipedia.org/wiki/... [wikipedia.org]
Of course the colours are only virtual - a mental construct - two mark two kinds of nodes.
Re: (Score:2)
You are Technically correct... The best kind of correct.
But in real life, when dealing with Maps we focus on 1 layer 2d Maps. Because otherwise we will need to travel across different mediums.
Re: (Score:2)
Incorrect. Due to the possibility of enclaves, four colors may not be enough for a 1-layer, 2-dimensional map.
Re: (Score:3)
Re: (Score:3)
Four is sufficient for any planar graph on a genre 0 surface (flat plane, surface sphere, surface of other solid with no holes). If I recall correctly, seven are required to colour any planar graph on a genre 1 surface (surface of a solid with a single hole, like a torus or donut).
Risk is the way (Score:2)
Re: (Score:2)
Single node can have more than 3 interconnections and each of those do not need distinct color. Just different from said node and its neighbors.
It was proven, after 125 years that that is the case. And in those 125 years nobody found a map that would need more than 4. Just nobody could prove that such map doesn't exist. So, your "very simple exercise in logic" is wrong.
https://www.youtube.com/watch?... [youtube.com]
Re: (Score:1)
Re: (Score:1)
> If a single node has more than 3 interconnects, 4 colours cannot be enough.
Um, no. You fail. Try harder next time!
In Soviet Russia ... (Score:2)