Timeline for Proving a theorem on coloring a peculiar graph
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 25, 2019 at 17:20 | history | edited | Gabe Conant | CC BY-SA 4.0 |
edited body
|
| Jun 25, 2019 at 16:19 | comment | added | vidyarthi | thanks! that was what irritated me. How could such a hard problem admit such an easy solution! So now i am satisfied(although problem is unsolved), but see here though | |
| Jun 25, 2019 at 16:15 | comment | added | Gabe Conant | @vidyarthi I added a picture of $H$. The intuition behind your idea was that there couldn't be a subgraph of $G$ consisting only of vertices that join two of the cliques. This seems reasonable for $k=3$ or $k=4$, or in the case that the cliques don't "intertwine" too much (e.g., if $G$ is planar like in Wikipedia article for the conjecture). But for $k=5$ there is enough room to allow the cliques to intertwine enough. Combined with the guess that there wouldn't be such an easy proof of a $500 Erdos problem, the only thing left to do was a brute force drawing. | |
| Jun 25, 2019 at 16:10 | comment | added | vidyarthi | how did you come up with this example? | |
| Jun 25, 2019 at 16:09 | history | edited | Gabe Conant | CC BY-SA 4.0 |
added 261 characters in body
|
| Jun 25, 2019 at 16:05 | vote | accept | vidyarthi | ||
| Jun 25, 2019 at 16:03 | comment | added | vidyarthi | thanks! got it, but please draw the graph $H$ so that it is clearly visible | |
| Jun 25, 2019 at 16:02 | vote | accept | vidyarthi | ||
| Jun 25, 2019 at 16:05 | |||||
| Jun 25, 2019 at 15:57 | comment | added | vidyarthi | It is clearly seen that there are many green vertices which do not have five degree. Could you draw the nine vertex subgraph outside for more specificity | |
| Jun 25, 2019 at 15:51 | comment | added | Gabe Conant | @vidyarthi Each of the green vertices is connected to at least 5 other green vertices (once we account for all of the edges in the cliques that I haven't drawn). Is this what you are asking? | |
| Jun 25, 2019 at 15:47 | comment | added | vidyarthi | But the induced subgraph formed by those very vertices will not have at least $5$ degree, because, when we remove those nine vertices, their adjacency will be only with respect to those nine vertices, but their adjacency with respect to other vertices(in the clique of which they are a part of) will not be there right? | |
| Jun 25, 2019 at 15:43 | comment | added | vidyarthi | Thanks, can we give a smaller counterexample? | |
| Jun 25, 2019 at 15:42 | vote | accept | vidyarthi | ||
| Jun 25, 2019 at 15:45 | |||||
| Jun 25, 2019 at 15:30 | history | edited | Gabe Conant | CC BY-SA 4.0 |
added 88 characters in body
|
| Jun 25, 2019 at 15:25 | history | answered | Gabe Conant | CC BY-SA 4.0 |