most recent 30 from http://mathoverflow.net 2013-05-19T22:00:24Z http://mathoverflow.net/feeds/question/101873 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/101873/a-ramsey-like-lower-bound András Salamon 2012-07-10T18:21:44Z 2012-07-10T21:06:58Z

<blockquote> <p>Does there exist a graph $G$ which cannot be properly vertex-coloured with 3 colours (i.e. $G$ has chromatic number at least 4), such that for every graph $H$, if $H$ contains a triangle but there is no graph homomorphism from $G$ to $H$, then $H$ must contain at least as many vertices as $G$?</p> </blockquote> <p>This question arose from an application in computational complexity. Any pointers to similar results would be welcome, or a hint if this is trivial. I am familiar with Hell and Nešetřil's textbook <em>Graphs and Homomorphisms</em> and the classic constructions of rigid graphs by Chvátal et al. and Nešetřil/Rödl, but am not an expert in graph theoretic combinatorics.</p> <h2>Motivation</h2> <p>In some sense, this problem seeks a lower bound on the size of graphs $H$ which contain a triangle but which are also not homomorphic images of $G$. This compares to the usual Ramsey requirement, which can be phrased in terms of bounding the size of graphs which guarantee the presence of large enough complete subgraphs, or the absence of homomorphic images of large enough complete graphs.</p> <p>The linear relationship between the order of $G$ and $H$ is the first "interesting" one. If the bound is decreased by 1, requiring only $|V(H)| \ge |V(G)| - 1$, then $G = K_4$ suffices but the size condition on $H$ holds simply because $H$ contains a triangle. I would also be interested in extensions, such as establishing whether such a graph $G$ exists for other functions bounding the order of $H$ in terms of the order of $G$.</p>

http://mathoverflow.net/questions/101873/a-ramsey-like-lower-bound/101891#101891 James Cranch 2012-07-10T21:06:58Z 2012-07-10T21:06:58Z

<p>I'm confused. Take $H$ to be the triangle. Since $G$ is not three-colourable, there is no map from $G$ to $H$, and $H$ contains a triangle.</p>