4 ms·
Can someone ELI5 the real world applications of this? I don't know many people who spend their time coloring graphs, let alone needing to know how many colors a
by yosito 6y ago
Can someone ELI5 the real world applications of this? I don't know many people who spend their time coloring graphs, let alone needing to know how many colors are needed to color them.
- boomboomsubban 6y agoMath doesn't necessarily consider the real world applications. That said you can represent almost anything as a graph, and "how many different x will we need for y" is a fairly common question. This provides the answer for certain kinds of y.
- ColinWright 6y agoGraph colouring is NP-Complete, and many real world problems map fairly naturally to it. I wrote a program that factors integers by colouring graphs as a demonstrator, but it's easy enough to use colouring to solve SAT problems. In compiler technology, "register colouring" is a thing, although no longer necessarily the best technique to solve the particular problem. Optimal Route Computation can be cast as a graph colouring problem, as can scheduling. I recorded a talk about this some time ago in which I proved that G3C (Graph 3-Colouring) is NPC, let me know if you'd like a link and I'll see if it's still available. If not, I'm giving it again as a part of the G4G Celebration of Mind series of talks.
- gameswithgo 6y agographs are used all the time in programming. knowing more about them could prove useful to someone sometime. Also may never be useful.
- concreteblock 6y agoMany problems can be reduced to graph coloring problems if you look at it the right way. Try understanding the standard examples (see the applications section in Wikipedia), then it is really easy to come up with your own applications.