"The Micro-world of Cographs", Alecu, Lozin, and de Werra, IWOCA 2020, recently caught my attention.

Cographs ( have a simple structure, but there's still an interesting hierarchy of subclasses of graphs within them restricting different parameters of graph complexity to be bounded.

A typical result: Every cograph with large h-index must contain a large complete graph, balanced bipartite graph, or forest of many high-degree stars.

@11011110 That's a well-written article, very inviting for the reader.

My first graph theory class gave us, as an exercise, the problem of proving that the family generated from vertices, disjoint union and complement is precisely the family of P4-free graphs. I remember working hard on that; I'm going to go out to the barn later and see if I can still find my write-up.

@11011110 I read only up through section 2. Can you tell me what justifies the term “cograph” for this class of graphs?

@mjd @11011110 Well, the complementation operation. Were you expecting a categorical "reverse all arrows" co-definition?

@JordiGH @mjd Yes, I'm pretty sure the term "cograph" was introduced by as a shorthand for "complement-reducible graphs". You can see the two names side-by-side in Corneil et al 1981 but apparently Lerchs was already calling them that in 1972.

An unrelated category-theoretic meaning of cographs was already used by Szabo in 1975 ( so confusion over this term is far from new.

@JordiGH @11011110 I was imagining (or hoping for) something more like the “codata” of section 4 of “Elementary Strong Functional Programming” (Turner 1995).

@mjd @11011110 I don't speak computation/logic very well, but this

"Codata definitions are equations over types that produce final algebras, instead of the initial algebras we get for data definitions,"

makes it sound like this really is about reversing arrows. I just don't know what those arrows might be.

@JordiGH @mjd Recursive algorithms compute data (finite sets of values) from complex inputs by mapping them downward, to simpler inputs. Corecursive algorithms compute codata (infinite sequences) from simple inputs by mapping them upward to more complex values.

A standard example is Fibonacci numbers. Recursion: fib(n)=fib(n-1)+fib(n-2), a combination of simpler values. Corecursion: generate the whole Fibonacci sequence from the simple base case (1,1) by repeatedly replacing (a,b) by (b,a+b).

Sign in to participate in the conversation

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!