This is the graph ‘HCRbdq{‘ from an earlier post. The number of vertices at even distance from vertex 8 is 4, and the number of edges in the subgraph induced by these vertices is 1. So the even-minus-even-horizontal invariant is no less than 3. Checking the other vertices, you find that there is no other vertex where the number of vertices at even distance minus the number of induced edges is more. So even-minus-even-horizontal invariant for this graph is 3. The independence number is also three.

So what is needed here is an efficiently checkable characterization of graphs where these invariants are equal. This would yield a new -property – and would “solve” this difficult graph.

Advertisements