patternMinor
4-color to 3-color polynomial reduction
Viewed 0 times
colorreductionpolynomial
Problem
I know a simple reduction from 3-color to 4-color. But how do you reduce 4-color to 3-color ?
I have been searching for the right way to make this reduction for a while now. I would love some pointers.
I have been searching for the right way to make this reduction for a while now. I would love some pointers.
Solution
For a more general reduction, László Lovász [1] proved that
COLORABILITY reduces to 3-COLORABILITY
The COLORABILITY problem is defined as follows:
Input: A graph $G$ and a positive integer $k$.
Problem: Is $G$ $k$-colorable?
That is, the reduction given by László Lovász is applicable to any $k$ ($k \ge 4$).
However, this reduction is quite intricate. You can find an excellent explanation by Vašek Chvátal here. Please free feel to ask if you have some difficulty in understanding this reduction.
[1] Coverings and coloring of hypergraphs, Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Utilitas Math., Winnipeg, Man., 1973.
COLORABILITY reduces to 3-COLORABILITY
The COLORABILITY problem is defined as follows:
Input: A graph $G$ and a positive integer $k$.
Problem: Is $G$ $k$-colorable?
That is, the reduction given by László Lovász is applicable to any $k$ ($k \ge 4$).
However, this reduction is quite intricate. You can find an excellent explanation by Vašek Chvátal here. Please free feel to ask if you have some difficulty in understanding this reduction.
[1] Coverings and coloring of hypergraphs, Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Utilitas Math., Winnipeg, Man., 1973.
Context
StackExchange Computer Science Q#37967, answer score: 5
Revisions (0)
No revisions yet.