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/

Improve this question
$\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$
    – Joseph O'Rourke
    Commented 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$
    – Gordon Royle
    Commented Jan 11, 2012 at 22:50
  • $\begingroup$ [email protected] $\endgroup$
    – Gordon Royle
    Commented Jan 23, 2012 at 23:10
  • $\begingroup$ Dear Gordon, thank you for your Email address. $\endgroup$
    – Shahrooz
    Commented Jan 24, 2012 at 11:23

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .