Timeline for When the vertex covering number is smaller than the chromatic number
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:19 | history | edited | CommunityBot |
replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
|
|
| Jan 29, 2015 at 15:18 | vote | accept | Dominic van der Zypen | ||
| Jan 29, 2015 at 15:16 | answer | added | Emil Jeřábek | timeline score: 4 | |
| Jan 29, 2015 at 14:07 | comment | added | Dominic van der Zypen | Thank you very much - can you post this as an answer so that I can accept it and we can close this thread? | |
| Jan 29, 2015 at 13:13 | comment | added | Emil Jeřábek | The linked argument actually shows that $\chi(G)\le1+\chi(C)$, where $C$ is the subgraph induced by a minimal vertex cover. So, $\tau(G)\ge\chi(G)$ unless $C$ is a clique. For much the same reason, $\tau(G)\ge\chi(G)$ unless one vertex from $V-C$ is connected to everyone in $C$. So, no, there isn’t such a graph. | |
| Jan 29, 2015 at 12:54 | history | asked | Dominic van der Zypen | CC BY-SA 3.0 |