most recent 30 from http://mathoverflow.net 2013-05-20T22:40:38Z http://mathoverflow.net/feeds/question/85404 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/85404/has-anyone-seen-this-sort-of-graph-property-used-before gordon-royle 2012-01-11T11:00:46Z 2012-01-23T19:45:58Z

<p>Consider the following property of a graph $G$:</p> <p>The graph $G$ has no independent cutset of vertices, $S$, such that the number of components of $G-S$ is more than $|S|$ (the size of $S$). </p> <p>(That is, cannot delete 1 vertex and leave 2+ components, cannot delete 2 independent vertices and leave 3+ components etc.)</p> <p>For some as-yet-unexplained reason, this property has arisen in a couple of questions relating to chromatic roots; needing a name we called this property $\alpha$-1-tough, which uses the notation from graph toughness plus the adjective $\alpha$ to indicate "independent".</p> <p>Basically we believe that $\alpha$-1-tough graphs are well-behaved with respect to chromatic polynomials; the evidence is that various small graphs that violate certain reasonably well-founded and natural conjectures are very clearly <em>NOT</em> $\alpha$-1-tough.</p> <p>Having failed miserably at all attempts to prove anything sensible using this property, I wondered if anyone anywhere has seen this, or a similar, graph property appear anywhere.</p> <p>(I have posted a longer article about this on my (shared) blog, but am not sure of the policy about posting links to your own stuff so I won't do so just in case.)</p> <p>Edit: The blog entry is <a href="http://symomega.wordpress.com/2012/01/06/chromatic-roots-the-multiplicity-of-2/" rel="nofollow">http://symomega.wordpress.com/2012/01/06/chromatic-roots-the-multiplicity-of-2/</a></p>

http://mathoverflow.net/questions/85404/has-anyone-seen-this-sort-of-graph-property-used-before/86475#86475 Martin Milanic 2012-01-23T19:45:58Z 2012-01-23T19:45:58Z

<p>A more relaxed notion of independent (or stable) cutsets -- in which the number of remaining components is not relevant -- was studied in relation to the chromatic number in a 1983 paper by Tucker, see <a href="http://dx.doi.org/10.1016/0095-8956(83)90039-4" rel="nofollow">http://dx.doi.org/10.1016/0095-8956(83)90039-4</a></p> <p>More recently, Brandstädt et al. proved that it is NP-complete to recognize whether a graph has a stable cutset even for restricted graph classes, see <a href="http://dx.doi.org/10.1016/S0166-218X(00)00197-9" rel="nofollow">http://dx.doi.org/10.1016/S0166-218X(00)00197-9</a></p>