Talk:Split graph

The number of partitionings

In the article: "...can be partitioned in three different ways". At the same time Tyshkevich (1990) says that any split graph G allows at most 2 partitions. I am wondering how the two statements can be reconciled. In terms of isomorphism, maybe? - Altenmann >talk 23:11, 7 November 2023 (UTC)

It appears to mean that there are at most two isomorphism classes of splits. A complete graph $K_{n}$ can be split into $(n,0)$ or $(n-1,1)$, but although there are $n$ different $(n-1,1)$ splits when considered on labeled graphs, they are all isomorphic. —David Eppstein (talk) 23:45, 7 November 2023 (UTC)

Does it make sense to add this factoid to the article? Tyshkevich (1990) refers the proof of it to her doktor nauk thesis. - Altenmann >talk 00:40, 8 November 2023 (UTC)

P.S. In the reflist in Tyshkevich (1990) I noticed the term "box-threshold graphs". While googling the term I run into a whole snake den: matroidal graph, matrogenic graph, domishold graph, pseudo-split graph, p-threshold graph, mock threshold graph . Redlinks... - Altenmann >talk 00:58, 8 November 2023 (UTC)

P.P.S. This reminded me that a long time ago, in 1970s or 80s, I run into a hilarious article in ACM SIGACT News bulletin, named something like "On patriotic graphs", a mockery on proliferation of graph types of little apparent use. It started with the definition of patriotic graph as being colorable in three colors, red, white, and blue, and proceeded with defining more and more refined categories, like, "A maximal patriotic graph is a graph adding to which any edge makes it unpatriotic", crowned with the theorem something like "Semirigid transposable polyspastic absorbent fungible equimetric maximal patriotic graphs exist." Every 4-5 years I surf the internets for this article, in vain. Today I noticed there is an online archive of SIGACT News, much of it is non-OCR, unfortunately, and maybe I will browse it... - Altenmann >talk 01:25, 8 November 2023 (UTC)