Vertex arboricity of cographs

C\'esar Hern\'andez Cruz; Pavol Hell; Payam Valadkhan; Sebasti\'an Gonz\'alez Hermosillo de la Maza; Seyyed Aliasghar Hosseini

arxiv: 1907.07286 · v1 · pith:GVIODL3Lnew · submitted 2019-07-16 · 🧮 math.CO · cs.DM

Vertex arboricity of cographs

Sebasti\'an Gonz\'alez Hermosillo de la Maza , Pavol Hell , C\'esar Hern\'andez Cruz , Seyyed Aliasghar Hosseini , Payam Valadkhan This is my paper

Pith reviewed 2026-05-24 20:34 UTC · model grok-4.3

classification 🧮 math.CO cs.DM

keywords cographsarboricitydynamic programmingcotreesvertex partitionsforestsindependent setsobstructions

0 comments

The pith

Cographs admit a polynomial-time dynamic programming algorithm to decide partitions into p forests and q independent sets.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that cographs, built recursively via disjoint unions and joins, support dynamic programming over their cotree to decide whether vertices can be split into any fixed number p of forests and q of independent sets. The same procedure also computes maximum q-colorable subgraphs, maximum arboricity-p subgraphs, minimum feedback vertex sets, and minimum q-colorable feedback vertex sets. A sympathetic reader would care because these partitioning tasks are NP-hard on general graphs yet become tractable on cographs, a class containing many recursively defined structures. For the special case of two forests the authors list all minimal forbidden cographs; for larger p the obstructions proliferate exponentially but remain bounded in size and cotree height.

Core claim

We give a polynomial-time dynamic programming algorithm for deciding whether a given cograph admits a vertex partition into p forests and q independent sets; the algorithm also solves maximum q-colourable subgraph, maximum subgraph of arboricity p, minimum vertex feedback set, and minimum q of a q-colourable vertex feedback set.

What carries the argument

Dynamic programming over the cotree whose nodes are disjoint-union or join operations, with states that track feasible assignments of each subtree's vertices to the p forests and q independent sets.

If this is right

For any fixed p and q the decision problem is solvable in polynomial time on cographs.
The same procedure yields polynomial-time solutions for maximum q-colourable subgraph and maximum arboricity-p subgraph on cographs.
Minimum feedback vertex set and minimum q-colourable feedback vertex set are polynomial-time solvable on cographs.
When p equals 2 there exists a finite list of minimal cograph obstructions to arboricity 2.
For larger p the number of minimal obstructions grows exponentially while their size and cotree height remain bounded.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same state-combination technique could be reused for other partition problems into bounded-density subgraphs on cographs.
Exact arboricity computation on cographs becomes polynomial-time for every fixed target value.
Obstruction sets for related parameters such as linear arboricity may admit similar exponential-size but bounded-height descriptions.

Load-bearing premise

The number of states needed to combine solutions at each cotree node stays polynomial in the fixed parameters p and q.

What would settle it

A concrete cograph together with specific p and q where running the described dynamic program on its cotree produces a yes/no answer that differs from the true existence of such a partition.

read the original abstract

Arboricity is a graph parameter akin to chromatic number, in that it seeks to partition the vertices into the smallest number of sparse subgraphs. Where for the chromatic number we are partitioning the vertices into independent sets, for the arboricity we want to partition the vertices into cycle-free subsets (i.e., forests). Arboricity is NP-hard in general, and our focus is on the arboricity of cographs. For arboricity two, we obtain the complete list of minimal cograph obstructions. These minimal obstructions do generalize to higher arboricities; however, we no longer have a complete list, and in fact, the number of minimal cograph obstructions grows exponentially with arboricity. We obtain bounds on their size and the height of their cotrees. More generally, we consider the following common generalization of colouring and partition into forests: given non-negative integers $p$ and $q$, we ask if a given cograph $G$ admits a vertex partition into $p$ forests and $q$ independent sets. We give a polynomial-time dynamic programming algorithm for this problem. In fact, the algorithm solves a more general problem which also includes several other problems such as finding a maximum $q$-colourable subgraph, maximum subgraph of arboricity-$p$, minimum vertex feedback set and minimum $q$ of a $q$-colourable vertex feedback set.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a solid cotree DP for (p,q)-partitions into forests and independent sets on cographs plus the full minimal obstruction list for arboricity exactly 2.

read the letter

The main takeaway is that this work supplies a polynomial-time DP on cotrees that decides whether a cograph admits a partition into p forests and q independent sets. The same routine also handles maximum q-colorable subgraph, maximum arboricity-p subgraph, minimum feedback vertex set, and a couple of mixed variants. For the special case of arboricity 2 they list every minimal cograph obstruction; the list is finite and they prove it is complete. Both results are new relative to the cited literature on cograph coloring and arboricity. The approach is straightforward once you have the cotree: at union nodes you add the counts, at join nodes you enforce that forests stay within one side and independent sets cannot use both sides. The state stays polynomial in p and q because you only track vertex counts per forest or color class, not connectivity details; the join operation already forbids cross edges. That part checks out cleanly. The exponential growth in the number of obstructions for larger arboricity is stated and bounded by cotree height, which is unsurprising and not presented as a surprise. No load-bearing gaps appear in the high-level argument, and the stress-test recurrences confirm there is no hidden exponential blow-up. This is standard but careful algorithmic work on a well-structured class. It will interest people who already care about cographs or about mixed coloring-arboricity problems. A reader working on parameterized algorithms or on other perfect-graph subclasses could extract the DP template. The paper is coherent on its own terms and the claims are grounded in explicit constructions rather than fitting. I would send it to a referee who knows cotrees and cograph DP; it is worth the time even if the referee asks for more explicit recurrence tables or a small computational check on the obstruction list.

Referee Report

0 major / 2 minor

Summary. The paper claims a polynomial-time dynamic programming algorithm on cotrees to decide if a cograph admits a partition of its vertices into p forests and q independent sets; the same algorithm solves maximum q-colourable subgraph, maximum arboricity-p subgraph, minimum vertex feedback set, and minimum q of a q-colourable feedback set. It also enumerates the complete list of minimal cograph obstructions for arboricity 2 and gives bounds on the number, size, and cotree height of minimal obstructions for higher arboricity.

Significance. If the central claims hold, the work supplies an explicit, polynomial-time solution for a natural common generalization of colouring and arboricity on cographs, together with a concrete obstruction list for the arboricity-2 case. The DP construction and the enumeration result are both contributions that can be directly used or extended in the study of sparse partitions on perfect graphs.

minor comments (2)

The abstract states that the DP state cardinality is polynomial in p and q; the main text should include a short explicit count of the states (or a reference to the precise recurrence) so that the polynomial bound is immediately verifiable without reconstructing the full table.
For the arboricity-2 obstruction list, a brief indication of how the enumeration was performed (e.g., by exhaustive generation up to a size bound derived from the cotree height) would strengthen the completeness claim.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and the recommendation to accept. The report accurately summarizes the main contributions regarding the polynomial-time DP algorithm for (p,q)-forest-coloring on cographs and the enumeration of minimal obstructions for arboricity 2.

Circularity Check

0 steps flagged

No significant circularity; explicit DP algorithm on cotrees

full rationale

The paper's central contribution is an explicit polynomial-time dynamic programming algorithm on the cotree representation of cographs that tracks vertex counts for p forests and q independent sets, with additive merging at union nodes and cross-edge restrictions at join nodes. The state space is stated to remain polynomial in p and q, and the recurrences are defined directly from the cotree operations without any reduction to fitted parameters, self-citations, or renamed empirical patterns. The enumeration of minimal obstructions for arboricity 2 and the size/height bounds for higher values are obtained by exhaustive structural analysis of the same cotree model rather than by any self-referential construction. No load-bearing step collapses to a definition or prior self-citation; the derivation is self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the standard structural fact that cographs admit cotree decompositions whose only operations are disjoint union and join; no free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)

domain assumption Every cograph has a cotree representation using only disjoint-union and join nodes.
Invoked implicitly when the DP is defined on cotrees and when obstructions are described via cotree height.

pith-pipeline@v0.9.0 · 5799 in / 1335 out tokens · 17635 ms · 2026-05-24T20:34:38.296356+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We give a polynomial-time dynamic programming algorithm for deciding whether a given cograph admits a vertex partition into p forests and q independent sets

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.