9
$\begingroup$

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/

$\endgroup$
4
  • 1
    $\begingroup$ I think you should link to the relevant blog entry. Anyone who wants to investigate this would appreciate knowing more details. $\endgroup$ Jan 11, 2012 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$ Jan 11, 2012 at 22:50
  • $\begingroup$ [email protected] $\endgroup$ Jan 23, 2012 at 23:10
  • $\begingroup$ Dear Gordon, thank you for your Email address. $\endgroup$
    – Shahrooz
    Jan 24, 2012 at 11:23

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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