Add split graph recognition

[jplauri]

Given that there are many recognition algorithms available in IGraphM (for e.g., perfect graphs, chordal graphs, cacti), it would be natural to add more recognition algorithms - perhaps particularly for subclasses of perfect graphs.

One such popular class is split graphs. The Wikipedia article gives also a fast and straightforward recognition algorithm based on degree sequences. In Mathematica, one could implement this as:

g = Graph[{1 \[UndirectedEdge] 4, 1 \[UndirectedEdge] 5, 
   2 \[UndirectedEdge] 3, 2 \[UndirectedEdge] 4, 
   2 \[UndirectedEdge] 5, 3 \[UndirectedEdge] 4, 
   3 \[UndirectedEdge] 5, 4 \[UndirectedEdge] 5}]

dd = Sort[VertexDegree[g], Greater];
m = 0;
For[i = 1, i <= Length[dd], ++i,
 If[dd[[i]] >= i - 1, m = i]
 ]
Total[dd[[1;;m]]] == m*(m - 1) + Total[dd[[m + 1;;]]]

In this example, the input graph is indeed a split graph (i.e., it can be partitioned into a clique and an independent set).

I am sure there's a more idiomatic replacement for the ugly for-loop but I'm not sure what that is at the moment.

Anyway, is there any interest in adding such functionality? If so, where should I look to help open a PR for adding this functionality as e.g., SplitQ?

[szhorvat]

Thanks for the suggestion, I'll add this for the next release.

[szhorvat]

This is the first time that someone wanted to contribute code. Unfortunately, setting up the package is not that trivial. I'll look into making it easier, at least on Mac and Linux.

[jplauri]

I figured that might be the case, but I still at least tried to make this a little less time consuming for you by adding some code for inspiration :-)

I have a few more ideas as to what could be added but I can get back to you later on.

[szhorvat]

@jplauri Any opinions on implementing a directed generalization? https://www.sciencedirect.com/science/article/pii/S0012365X11005917

[jplauri]

I've never really worked much with digraphs in general myself, but if this is also simple enough to implement, I agree it could be nice to have for the user.