Foldable vertices & new Difficult Graph

Fomin et al proved that a graph G with a foldable vertex v (one whose neighbors don’t induce an anti-triangle) can be converted or folded to create a graph G’ such that \alpha(G)=1+\alpha(G').  In the case where the number of anti-edges in N(v) is less than |N[v]|, folding results in a graph G’ with fewer vertices than G. In this case G is reducible. Vertex v3 of GCRdro is foldable. N(v3) has no anti-triangles, and 2 anti-edges, while |N[v3]|=4. So this graph is reducible.

We have now completely switched over to using Patrick’s INP code (which is publicly available on Github). We just added the property of being foldable and reducible to the alpha-properties. The next difficult graph is GCR~vo. Here’s a figure.  You can find lots of interesting data about this graph by going to the link on the Difficult Graphs page. In particular alpha=3 but the best lower bound is 2. We need another lower bound for alpha that gives 3 for this graph.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s