Timeline for Cancelling a graph join from a graph homomorphism
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 19, 2017 at 10:15 | comment | added | Peter Heinig | @IlyaBogdanov: thanks for pointing out. While it is probably not my deleted answer that you are commenting on, your comment applies to it, too (since I erroneously used $K=K^1$). For those who still can read the deleted answer: this happened because for irrelevant reasons I was holding the (erroneous) belief 'all wheel graphs are perfect' (which is evidently false for odd-spoked wheels since the peripheral circuit constitutes an 'odd hole'), and then started to 'synthetically reason' with this erroneous belief. (The three-spoke wheel btw is indeed exceptional in that it has clique number 4). | |
| Sep 18, 2017 at 17:24 | comment | added | Ilya Bogdanov | To repeat a comment to a deleted answer. The case of $K$ complete is in fact much easier, since the vertices of $K$ in both $G+K$ and $H+K$ are dominating (=connected to everyone elde). Since the image of a dominating vertex cannot be anyone else's image, and all dominating vertices can be permuted via automorphisms, we may simply assume that the vertices of $K$, and only them, are mapped to the vertices of $K$. | |
| Sep 18, 2017 at 17:18 | vote | accept | Tobias Fritz | ||
| Sep 18, 2017 at 16:24 | answer | added | Ilya Bogdanov | timeline score: 13 | |
| Sep 18, 2017 at 15:52 | history | edited | Tobias Fritz | CC BY-SA 3.0 |
clarification
|
| Sep 18, 2017 at 15:51 | comment | added | Tobias Fritz | @IlyaBogdanov: Sure. I was assuming that finiteness would be clear from the context, but I'll make it explicit in the question. | |
| Sep 18, 2017 at 15:50 | comment | added | Tobias Fritz | @PeterHeinig: Good point about the chromatic numbers. I guess the same applies to the clique numbers, i.e. $\omega(G)\leq\omega(H)$, so that $G\to H$ also follows when $G$ is complete. So far, I haven't done much of a search on small instances. | |
| Sep 18, 2017 at 15:37 | comment | added | Peter Heinig | [..] we have proved that if $G+K\to H+K$, then $\chi(G)\leq \chi(H)$, hence $G\to K^{{\Large\chi(H)}}$. It follows that: if there is a counterexample to the implication you are asking about, then $H$ must be non-complete. Have you searched around among small such instances? | |
| Sep 18, 2017 at 15:35 | comment | added | Peter Heinig | Worth pointing out: we have (the inequality $\leq$ follows by retaining optimal colorings, while the inequality $\geq$ follows because if $\chi(G+K) < \chi(G) + \chi(K)$, then choose any such hypothetical coloring and notice that one of the two summands then would be colored with less colors than its chromatic number allows, which is impossible) the equality $\chi(G+K) = \chi(G) + \chi(K)$. Moreover, in general, if $X\to Y$, then $\chi(X)\leq\chi(Y)$. We now put this together. If $G+K\to H+K$, then $\chi(G)+\chi(K) = \chi(G+K)\leq\chi(H+K)=\chi(H)+\chi(K)$, hence $\chi(G)\leq\chi(H)$. So [..] | |
| Sep 18, 2017 at 14:36 | history | asked | Tobias Fritz | CC BY-SA 3.0 |