Digraphs icon indicating copy to clipboard operation
Digraphs copied to clipboard

Add `IsCograph`

Open wilfwilson opened this issue 2 years ago • 0 comments

See https://en.wikipedia.org/wiki/Cograph#Other_characterizations for several equivalent definitions. The simplest seems to be 'graph (i.e. symmetric digraph) that doesn't contain the 4-vertex path graph as a subgraph'.

I don't know how hard it is to implement this, I'm not familiar with any existing algorithms, but it looks like something that people have looked into before, see e.g. “A simple linear time algorithm for cograph recognition”.

wilfwilson avatar Nov 15 '21 12:11 wilfwilson