Timeline for Contracting 2 edges
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Aug 20, 2016 at 12:20 | comment | added | Dominic van der Zypen | Interesting comment, thank you! I don't quite see yet how to use this for answering the question, but maybe there is a way. | |
| Aug 20, 2016 at 2:01 | comment | added | user44191 | Something interesting I noticed, not sure if it helps: A graph has a clique of $n - 1$ vertices if and only if its complement has no two edges without vertices in common and no triangles. For a graph as you describe, any subgraph given by removing a triangle or by removing two edges without vertices in common must also have decreased chromatic number. | |
| Aug 19, 2016 at 7:55 | history | asked | Dominic van der Zypen | CC BY-SA 3.0 |