Timeline for Hardness of approximating fractional chromatic number on bounded degree graphs
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 2, 2011 at 20:01 | history | edited | Jukka Suomela | CC BY-SA 3.0 |
added 9 characters in body
|
| Nov 2, 2011 at 19:56 | comment | added | Jukka Suomela | @AndrewD.King: Yes, I'll edit the answer; it'll hopefully make more sense that way. :) | |
| Nov 2, 2011 at 19:37 | comment | added | Andrew D. King | @JukkaSuomela I mean that as stated, this does not prove APX-hardness. E.g. it is well-known (Holyer, SICOMP, 1980) that determining the chromatic index of a cubic graph is NP-hard, meaning that it is NP-hard to determine whether or not the chromatic number of a line graph with maximum degree 4 is 4. What I think you mean is: Given any constant $k$, there exist constants $\Delta$, $c_1$, and $c_2$ such that $kc_1<c_2$,... Is that right? | |
| Nov 2, 2011 at 15:10 | comment | added | Jukka Suomela | @AndrewD.King: Right, you can make any of them arbitrarily large, etc. But perhaps you could post an answer that shows that the simple version of the corollary can be derived by using older and easier techniques – I think it would already be sufficient to answer OP's question? | |
| Nov 2, 2011 at 15:03 | comment | added | Andrew D. King | Surely the last corollary has some other modifiers on the constants, otherwise this is very well known for small values of $\Delta$, $c_1$, and $c_2$... | |
| Nov 2, 2011 at 14:59 | vote | accept | Ashwinkumar B V | ||
| Nov 2, 2011 at 10:36 | history | answered | Jukka Suomela | CC BY-SA 3.0 |