most recent 30 from http://mathoverflow.net 2013-05-26T04:14:33Z http://mathoverflow.net/feeds/user/12836 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/49555/is-the-following-graph-well-known/54922#54922 Jon Noel 2011-02-09T20:19:50Z 2011-02-09T20:19:50Z

<p>If anyone is interested, here is a link to a paper that deals with graphs that are similar to (but more general than) Johnson Graphs: <a href="http://arxiv.org/abs/0910.4774" rel="nofollow">arXiv</a>. It doesn't answer the question though, just an interesting paper that is somewhat relevant to this topic. </p>

http://mathoverflow.net/questions/40230/what-are-some-good-examples-of-non-monotone-graph-properties/54837#54837 Jon Noel 2011-02-09T01:08:31Z 2011-02-09T01:08:31Z

<p>Some variations of colouring problems are not monotone. For example, consider the following problem from <a href="http://dx.doi.org/10.1016/j.disc.2007.07.028" rel="nofollow">ScienceDirect</a>. </p> <p>For a fixed graph $G$ and integer $k\geq\chi(G)$ consider the $k$-colour graph $\mathscr{C}_k(G)$ on the set of all $k$-colourings of $G$ where colourings $f$ and $g$ are adjacent if $f(v)\neq g(v)$ for exactly one vertex $v$ of $G$. Say that $G$ is $k$-mixing if the $k$-colour graph is connected.</p> <p>For $n\geq3$ the complete bipartite graph $K_{n,n}$ is $k$-mixing whenever $k\geq3$, but the <a href="http://mathworld.wolfram.com/CocktailPartyGraph.html" rel="nofollow">cocktail party graph</a> with $n$ couples (obtained by deleting edges from $K_{n,n}$) is not $n$-mixing. See the examples in the <a href="http://dx.doi.org/10.1016/j.disc.2007.07.028" rel="nofollow">paper</a> above.</p>