# Has anyone seen this sort of graph property used before?

Consider the following property of a graph $G$:

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$).

(That is, cannot delete 1 vertex and leave 2+ components, cannot delete 2 independent vertices and leave 3+ components etc.)

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".

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 NOT $\alpha$-1-tough.

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.

(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.)

Edit: The blog entry is http://symomega.wordpress.com/2012/01/06/chromatic-roots-the-multiplicity-of-2/

-
I think you should link to the relevant blog entry. Anyone who wants to investigate this would appreciate knowing more details. – Joseph O'Rourke Jan 11 '12 at 13:26
Ok, now added... just didn't want anyone to think that I'm trying to drive traffic to my blog (not that there would be any point). – Gordon Royle Jan 11 '12 at 22:50
gordon.royle@uwa.edu.au – Gordon Royle Jan 23 '12 at 23:10

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 http://dx.doi.org/10.1016/0095-8956(83)90039-4

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 http://dx.doi.org/10.1016/S0166-218X(00)00197-9

-