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/

| cite | improve this question | | | | |
  • 1
    $\begingroup$ I think you should link to the relevant blog entry. Anyone who wants to investigate this would appreciate knowing more details. $\endgroup$ – Joseph O'Rourke Jan 11 '12 at 13:26
  • $\begingroup$ 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). $\endgroup$ – Gordon Royle Jan 11 '12 at 22:50
  • $\begingroup$ gordon.royle@uwa.edu.au $\endgroup$ – Gordon Royle Jan 23 '12 at 23:10
  • $\begingroup$ Dear Gordon, thank you for your Email address. $\endgroup$ – Shahrooz Janbaz Jan 24 '12 at 11:23

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

| cite | improve this answer | | | | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.