A program to find families of graphs in Free$\{C_4,4K_1\}$ with bounded clique width

Alexandre Talon; Cl\'eoph\'ee Robin

arxiv: 2606.17307 · v1 · pith:7RJUSJBInew · submitted 2026-06-15 · 💻 cs.DM · math.CO

A program to find families of graphs in Free\{C₄,4K₁\} with bounded clique width

Cl\'eoph\'ee Robin , Alexandre Talon This is my paper

Pith reviewed 2026-06-27 02:17 UTC · model grok-4.3

classification 💻 cs.DM math.CO

keywords Free{C4, 4K1}clique width(k,l,m)-decompositioninduced subgraphsgraph coloringforbidden subgraphsbounded width

0 comments

The pith

If all graphs in a class are (k,l,m)-decomposable then the class has bounded clique width.

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

The paper introduces the (k,l,m)-decomposition as a sufficient condition for any graph class to have bounded clique width. It applies this to find subclasses of Free{C4, 4K1} with bounded clique width using a dedicated program. For graphs in this class that can be covered by three cliques, it constructs infinite families of supergraphs that have unbounded clique width. This matters because the coloring problem's complexity is open for the full Free{C4, 4K1} class, and bounded clique width would imply polynomial algorithms for many problems.

Core claim

The (k,l,m)-decomposition framework ensures bounded clique width for any class where every graph satisfies the decomposition property, and several families within Free{C4, 4K1} admit such decompositions while certain 3-clique-coverable graphs do not bound the clique width of their supergraphs.

What carries the argument

The (k,l,m)-decomposition, a structural property that allows recursive decomposition limiting the number of labels needed for clique width expressions.

If this is right

Some infinite families in Free{C4, 4K1} have bounded clique width.
Any (k,l,m)-decomposable class has bounded clique width, regardless of other properties.
For any 3-clique-coverable G in Free{C4, 4K1}, there exists an infinite family of supergraphs in the class with unbounded clique width.

Where Pith is reading between the lines

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

If the entire Free{C4, 4K1} class turns out to be (k,l,m)-decomposable for some parameters, then it would have bounded clique width and thus polynomial-time coloring.
The program used to search for such families could be adapted to other forbidden subgraph classes to identify bounded clique width cases.

Load-bearing premise

The definition of (k,l,m)-decomposition is crafted so that the bounded clique width follows directly for any class meeting the condition, without needing extra assumptions on the graphs.

What would settle it

A graph class that satisfies the (k,l,m)-decomposition for some fixed k,l,m but contains graphs with arbitrarily large clique width.

Figures

Figures reproduced from arXiv: 2606.17307 by Alexandre Talon, Cl\'eoph\'ee Robin.

**Figure 1.** Figure 1: Ninjagraph NG Given a family of graphs H and a graph H ∈ H, HH denotes the subclass of graphs in H that contain H as induced subgraph. In other words: HH = {G ∈ H : H ⊆i G}. Given a class of graphs G, we set HG = ∪G∈GHG. We consider the following question: How to find graphs H ∈ F ree{C4, 4K1} such that F ree{C4, 4K1} H are polynomial time colourable? Given three integers k, l, m we define the (k, l, m)-de… view at source ↗

**Figure 2.** Figure 2: cw(K4) = 2 1. Create a vertex u labeled with an integer ℓ. 2. Make the disjoint union of two already built graphs. 3. Add all the edges between all vertices with label i and all vertices with label j (i ̸= j). 4. Relabel all vertices of label i with label j. For example, it is possible to build the graph Kn using 2 labels (see [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** Figure 3: The Icosahedron Lemma 2.8. If G is a magic with respect to a class of graphs H then HG has bounded clique width and graphs in HG can be coloured in Polynomial time. In what follows, we will simply say that a graph is magic, meaning that it is magic with respect to Free{C4, 4K1}, the class of graphs we consider in this paper. To conclude this section, we illustrate the concept of (k, l, m)-decomposition wit… view at source ↗

**Figure 4.** Figure 4: (Temporary) Draw of H3 with G = C5 Suppose for a contradiction that Hn contains an induced C4. Let {v1, v2, v3, v4} be the vertices of the C4 with v1v2, v2v3, v3v4, v4v1 ∈ E(G). Since G ∈ Free{C4}, |{v1, v2, v3, v4} ∩ V (G)| ≤ 3. Suppose, first, that {v1, v2, v3, v4} ∩ Cn = Ø. By the previous observation, |{v1, v2, v3, v4} ∩ (An ∪ Bn)| ≥ 1. By symmetry, suppose that v1 = ak, for some k ≤ n. Observe that NH… view at source ↗

**Figure 5.** Figure 5: Graphs in Obs (Theorem 3.4) The first step is to generate all twin-free graphs in Free{C4, 4K1}. In a second time, the program takes each graph G generated previously and tries to find a (k, l, m)-decomposition for Free{C4, 4K1} G. We are only interested in graphs which contain at least one graph from the set Obs, so we implemented this feature in our program. Note that if the program does not find such a … view at source ↗

read the original abstract

In this paper we study the class of graphs without cycles of size 4 and independent sets of size 4 as induced subgraphs: $\mathop{Free}\{C_4, 4K_1\}$. This is one of the three minimal minimal open cases for the complexity of the colouring problem when restricted to classes defined by excluding induced subgraphs of order 4. We investigate the clique width of some subclasses of $\mathop{Free}\{C_4, 4K_1\}$. We introduce a new framework: the $(k,l,m)$-decomposition and prove that if all the graphs of a class $\cal G$ are $(k,l,m)$-decomposable, then graphs in $\cal G$ have bounded clique width. We give a few examples of such class, found with the help of a program we designed. We also show, for any graph $G \in \mathop{Free}\{C_4, 4K_1\}$ that is 3 cliques coverable, an infinite family in $\mathop{Free}\{C_4, 4K_1\}$ of supergraphs of $G$ which have unbounded clique width.

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 introduces a (k,l,m)-decomposition that implies bounded clique-width for any class where all graphs satisfy it, applies a program to find families in Free{C4,4K1}, and builds unbounded-cw supergraphs for some members of the class.

read the letter

The paper's main contribution is a new (k,l,m)-decomposition framework with a proof that any class in which every graph is (k,l,m)-decomposable has bounded clique-width. The authors use a custom program to identify some such families inside Free{C4,4K1} and separately construct, for any 3-clique-coverable G in the class, an infinite family of supergraphs that remain in the class but have unbounded clique-width.

The decomposition and the program appear to be original content rather than direct reductions of earlier results. The work focuses on one of the three minimal open cases for coloring complexity in induced-subgraph-free classes of order 4, which is a standard target in algorithmic graph theory. That choice of problem is reasonable.

The abstract states the central implication cleanly but supplies neither the definition of the decomposition nor a proof sketch, so the actual strength of the theorem cannot be checked from the summary. The program is mentioned without any output details or description of the families it produced, which makes it hard to gauge how useful the examples are. The unbounded supergraph construction is a clean negative result but sits apart from the positive decomposition claim.

No circularity is visible in the stated logic, and the theorem is presented as holding for arbitrary classes meeting the condition. This paper is aimed at researchers working on clique-width and coloring in hereditary classes. Readers interested in structural tools for the remaining open coloring cases would get value if the full details support the claims. It deserves a serious referee because the topic is central and the approach is concrete, even though the referee will need the decomposition definition and program results to assess the work properly.

Recommendation: send to peer review.

Referee Report

2 major / 2 minor

Summary. The paper studies the hereditary class Free{C₄, 4K₁} and introduces the (k,l,m)-decomposition framework. It proves that any class G in which every graph is (k,l,m)-decomposable has bounded clique-width. Using a custom program, it identifies concrete families inside Free{C₄, 4K₁} that admit such decompositions (hence bounded cw). It also constructs, for any 3-clique-coverable G in the class, an infinite family of supergraphs still in Free{C₄, 4K₁} that have unbounded clique-width.

Significance. If the central implication holds, the (k,l,m)-decomposition supplies a new, checkable sufficient condition for bounded clique-width that could be applied to other hereditary classes relevant to coloring complexity. The program provides a reproducible method for discovering bounded-cw subclasses, and the supergraph construction gives an explicit obstruction showing that the full class is not bounded-cw. These are concrete, falsifiable contributions to the structural theory of clique-width.

major comments (2)

[Main theorem and definition of (k,l,m)-decomposition] The central theorem (that (k,l,m)-decomposability implies bounded clique-width) is load-bearing for all subsequent claims. The manuscript must therefore contain an explicit, self-contained definition of the (k,l,m)-decomposition together with a complete proof of the implication; the abstract alone does not supply either, so the support for the theorem cannot be verified from the provided text.
[Program description and reported families] The program is used to certify that certain families are (k,l,m)-decomposable. The manuscript should therefore include the precise output of the program (or a machine-readable certificate) for at least one non-trivial family, together with a description of the search parameters and termination condition, so that the claimed bounded-cw examples can be independently checked.

minor comments (2)

[Introduction] Notation for the class Free{C₄, 4K₁} is introduced in the abstract but should be restated at the beginning of the introduction with a brief reminder of the induced-subgraph definition.
[Unbounded-cw supergraphs] The supergraph construction is stated for 3-clique-coverable graphs; the manuscript should clarify whether the same construction works for graphs with larger clique cover number or whether that case is left open.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need for greater explicitness and reproducibility. We address the two major comments below and will incorporate the requested clarifications in a revised version.

read point-by-point responses

Referee: [Main theorem and definition of (k,l,m)-decomposition] The central theorem (that (k,l,m)-decomposability implies bounded clique-width) is load-bearing for all subsequent claims. The manuscript must therefore contain an explicit, self-contained definition of the (k,l,m)-decomposition together with a complete proof of the implication; the abstract alone does not supply either, so the support for the theorem cannot be verified from the provided text.

Authors: The full manuscript contains both an explicit definition of the (k,l,m)-decomposition (in the section introducing the framework) and a complete proof that (k,l,m)-decomposability of every member of a class implies bounded clique-width. Nevertheless, we accept that these elements must be made more immediately verifiable. In the revision we will (i) state the definition in a dedicated, self-contained subsection with illustrative examples before any applications, (ii) present the central theorem and its proof in full detail immediately after the definition, and (iii) expand the abstract to give a concise outline of the definition and the implication. These changes will ensure the logical support is transparent without altering the theorem itself. revision: yes
Referee: [Program description and reported families] The program is used to certify that certain families are (k,l,m)-decomposable. The manuscript should therefore include the precise output of the program (or a machine-readable certificate) for at least one non-trivial family, together with a description of the search parameters and termination condition, so that the claimed bounded-cw examples can be independently checked.

Authors: We agree that the current description of the program is insufficient for independent verification. The revised manuscript will contain a new subsection that specifies: the exact search parameters (bounds on k, l, m and on graph order), the termination condition of the enumeration algorithm, and the concrete output (including a machine-readable certificate or explicit list of decompositions) for at least one non-trivial family. This material will be placed immediately after the description of the program and before the reported families, allowing any reader to reproduce or audit the bounded-clique-width claims. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The central theorem states that any class where every graph is (k,l,m)-decomposable has bounded clique-width, presented as a direct implication proved from the definition of the decomposition itself. No load-bearing step reduces by construction to a fitted input, self-citation chain, or renamed known result; the program-assisted examples and the separate construction of unbounded-cw supergraphs are independent of the implication and do not create self-referential loops. The derivation is self-contained against external benchmarks with no quoted reductions to prior author work or ansatzes.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper adds the (k,l,m)-decomposition concept and a computational search method; no free parameters or invented entities are mentioned.

axioms (1)

domain assumption If a class consists entirely of (k,l,m)-decomposable graphs then it has bounded clique width
This is the load-bearing theorem stated in the abstract.

pith-pipeline@v0.9.1-grok · 5758 in / 1167 out tokens · 39749 ms · 2026-06-27T02:17:43.429549+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

16 extracted references · 9 canonical work pages

[1]

Maffray, Frédéric and Morel, Grégory , urldate =. On. 2012 , langid =. doi:10.1137/110829222 , pages =

work page doi:10.1137/110829222 2012
[2]

Clique cutsets beyond chordal graphs , volume =

Boncompagni, Valerio and Penev, Irena and Vušković, Kristina , urldate =. Clique cutsets beyond chordal graphs , volume =. doi:10.1016/j.endm.2017.10.015 , pages =

work page doi:10.1016/j.endm.2017.10.015 2017
[3]

Coloring rings , volume =

Maffray, Frédéric and Penev, Irena and Vušković, Kristina , urldate =. Coloring rings , volume =. doi:10.1002/jgt.22635 , pages =

work page doi:10.1002/jgt.22635
[4]

Bondy, J. A. and Murty, U. S. R. , editorb =. Graph Theory , volume =
[5]

2007 , langid =

Theoretical Computer Science , author =. 2007 , langid =. doi:10.1016/j.tcs.2007.03.043 , pages =

work page doi:10.1016/j.tcs.2007.03.043 2007
[6]

2000 , issn =

Upper bounds to the clique width of graphs , journal =. 2000 , issn =. doi:https://doi.org/10.1016/S0166-218X(99)00184-5 , url =

work page doi:10.1016/s0166-218x(99)00184-5 2000
[7]

Clique-Width for 4-Vertex Forbidden Subgraphs , volume =

Brandstädt, Andreas and Engelfriet, Joost and Le, Hoang-Oanh and Lozin, Vadim , year =. Clique-Width for 4-Vertex Forbidden Subgraphs , volume =. Theory of Computing Systems , doi =
[8]

On the clique-width of (

Irena Penev , keywords =. On the clique-width of (. Discrete Applied Mathematics , volume =. 2020 , issn =. doi:https://doi.org/10.1016/j.dam.2020.07.009 , url =

work page doi:10.1016/j.dam.2020.07.009 2020
[9]

On the Relationship between Clique-Width and Treewidth

Corneil, Derek G.and Rotics, Udi. On the Relationship between Clique-Width and Treewidth. Graph-Theoretic Concepts in Computer Science. 2001

2001
[10]

Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics , year=

Maximum matching and a polyhedron with 0,1-vertices , author=. Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics , year=
[11]

Discrete Applied Mathematics , author =

Vertex coloring of graphs with few obstructions , url =. Discrete Applied Mathematics , author =. 2015 , file =

2015
[12]

Discrete Mathematics , author =

Coloring (. Discrete Mathematics , author =. 2023 , langid =. doi:10.1016/j.disc.2022.113225 , pages =

work page doi:10.1016/j.disc.2022.113225 2023
[13]

and Hamel, Angèle M

Fraser, Dallas J. and Hamel, Angèle M. and Hoàng, Chính T. and Holmes, Kevin and. Characterizations of (. Discrete Applied Mathematics , shortjournal =. 2017 , langid =. doi:10.1016/j.dam.2016.08.016 , pages =

work page doi:10.1016/j.dam.2016.08.016 2017
[14]

Nauchno-Technicheskaya Informatsiya , volume=

A reduction of a graph to a canonical form and an algebra arising during this reduction , author=. Nauchno-Technicheskaya Informatsiya , volume=
[15]

2021 , KEYWORDS =

Robin, Cléophée , URL =. 2021 , KEYWORDS =

2021
[16]

Hoàng and Nicolas Trotignon , keywords =

Chính T. Hoàng and Nicolas Trotignon , keywords =. A class of graphs with large rankwidth , journal =. 2024 , issn =. doi:https://doi.org/10.1016/j.disc.2023.113699 , url =

work page doi:10.1016/j.disc.2023.113699 2024

[1] [1]

Maffray, Frédéric and Morel, Grégory , urldate =. On. 2012 , langid =. doi:10.1137/110829222 , pages =

work page doi:10.1137/110829222 2012

[2] [2]

Clique cutsets beyond chordal graphs , volume =

Boncompagni, Valerio and Penev, Irena and Vušković, Kristina , urldate =. Clique cutsets beyond chordal graphs , volume =. doi:10.1016/j.endm.2017.10.015 , pages =

work page doi:10.1016/j.endm.2017.10.015 2017

[3] [3]

Coloring rings , volume =

Maffray, Frédéric and Penev, Irena and Vušković, Kristina , urldate =. Coloring rings , volume =. doi:10.1002/jgt.22635 , pages =

work page doi:10.1002/jgt.22635

[4] [4]

Bondy, J. A. and Murty, U. S. R. , editorb =. Graph Theory , volume =

[5] [5]

2007 , langid =

Theoretical Computer Science , author =. 2007 , langid =. doi:10.1016/j.tcs.2007.03.043 , pages =

work page doi:10.1016/j.tcs.2007.03.043 2007

[6] [6]

2000 , issn =

Upper bounds to the clique width of graphs , journal =. 2000 , issn =. doi:https://doi.org/10.1016/S0166-218X(99)00184-5 , url =

work page doi:10.1016/s0166-218x(99)00184-5 2000

[7] [7]

Clique-Width for 4-Vertex Forbidden Subgraphs , volume =

Brandstädt, Andreas and Engelfriet, Joost and Le, Hoang-Oanh and Lozin, Vadim , year =. Clique-Width for 4-Vertex Forbidden Subgraphs , volume =. Theory of Computing Systems , doi =

[8] [8]

On the clique-width of (

Irena Penev , keywords =. On the clique-width of (. Discrete Applied Mathematics , volume =. 2020 , issn =. doi:https://doi.org/10.1016/j.dam.2020.07.009 , url =

work page doi:10.1016/j.dam.2020.07.009 2020

[9] [9]

On the Relationship between Clique-Width and Treewidth

Corneil, Derek G.and Rotics, Udi. On the Relationship between Clique-Width and Treewidth. Graph-Theoretic Concepts in Computer Science. 2001

2001

[10] [10]

Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics , year=

Maximum matching and a polyhedron with 0,1-vertices , author=. Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics , year=

[11] [11]

Discrete Applied Mathematics , author =

Vertex coloring of graphs with few obstructions , url =. Discrete Applied Mathematics , author =. 2015 , file =

2015

[12] [12]

Discrete Mathematics , author =

Coloring (. Discrete Mathematics , author =. 2023 , langid =. doi:10.1016/j.disc.2022.113225 , pages =

work page doi:10.1016/j.disc.2022.113225 2023

[13] [13]

and Hamel, Angèle M

Fraser, Dallas J. and Hamel, Angèle M. and Hoàng, Chính T. and Holmes, Kevin and. Characterizations of (. Discrete Applied Mathematics , shortjournal =. 2017 , langid =. doi:10.1016/j.dam.2016.08.016 , pages =

work page doi:10.1016/j.dam.2016.08.016 2017

[14] [14]

Nauchno-Technicheskaya Informatsiya , volume=

A reduction of a graph to a canonical form and an algebra arising during this reduction , author=. Nauchno-Technicheskaya Informatsiya , volume=

[15] [15]

2021 , KEYWORDS =

Robin, Cléophée , URL =. 2021 , KEYWORDS =

2021

[16] [16]

Hoàng and Nicolas Trotignon , keywords =

Chính T. Hoàng and Nicolas Trotignon , keywords =. A class of graphs with large rankwidth , journal =. 2024 , issn =. doi:https://doi.org/10.1016/j.disc.2023.113699 , url =

work page doi:10.1016/j.disc.2023.113699 2024