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

1

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