REVIEW 4 major objections 5 minor 17 references
Characterization of Word-Representable Graphs using Modular Decomposition
T0 review · 4 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read Word-representability survives replacing a vertex by a module exactly when the module is a comparability graph, and this yields a full modular-decomposition characterization.
desk verdict Real progress on a Kitaev-Lozin open problem, but Theorems 3, 4, and 6 break for G=K1 and Theorem 3 lacks a proof; the main characterization should survive a small fix. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The operative construction is Ga[M], replacing a vertex a of G by a module M, a set of vertices that all have the same neighbors outside the set, so that M becomes a module in the resulting graph. The load-bearing theorem is Theorem 4, which reduces word-representability of the whole graph to word-representability of G and comparability of M; the mechanism is the universal-vertex observation that a neighbor of a is adjacent to all vertices of M, forcing M to be a comparability graph via [10, Theorem 9]. This local replacement then transfers to modular partitions, where the quotient graph G/P together with the induced modules G[Mi] reconstruct G, and yields the maximum formula for representation numbers.
What would settle it
Take G to be the one-vertex graph and M the 5-cycle C5. Then Ga[M] is C5, which is word-representable, while M is not a comparability graph; this contradicts the 'only if' direction of Theorem 4, showing the missing non-triviality assumption is essential.
Extended reading notes
Core claim
The central discovery is Theorem 4: for a connected graph G with a vertex a and a graph M, the graph Ga[M] obtained by replacing a with M is word-representable if and only if G is word-representable and M is a comparability graph. The proof combines a known sufficient condition with a universal-vertex argument: because G is connected, a has a neighbor b, and b is adjacent to every vertex of M in Ga[M], which forces M to be a comparability graph by an existing theorem. The same mechanism gives the lexicographical product characterization and, using the uniqueness of the maximal modular partition, the global characterization: a decomposable graph is word-representable precisely when each of its modules in a modular partition is a comparability graph and the quotient graph is word-representable, with the representation number equal to the maximum of the quotient's representation number and the modules' permutation-representation numbers.
Load-bearing premise
The proof requires the vertex being replaced to have at least one neighbor, because a neighbor of the replaced vertex is the universal vertex that forces the module to be a comparability graph; when that vertex is isolated or the graph is a single vertex, the stated characterization is false.
Editorial extensions
If this is right
- The lexicographical product G[G'] is word-representable if and only if G is word-representable and G' is a comparability graph, resolving the open problem about products.
- A decomposable graph is word-representable exactly when each module in a modular partition is a comparability graph and the quotient graph is word-representable.
- For a word-representable decomposable graph, $R(G) = \max\{R(G/P), R_p(G[M_1]), \ldots, R_p(G[M_k])\}$.
- Replacing a vertex by a comparability module preserves word-representability and lifts the representation number to the maximum of the two relevant numbers.
- A polynomial-time test for non-word-representability follows: compute the maximal modular partition, check whether all modules are comparability graphs, and if one is not, the graph is not word-representable.
Reading between the lines
- Implicit in the results but not stated in the paper, the main theorems require the replaced vertex to have at least one neighbor; a natural repair is to state that condition explicitly or restrict to non-trivial modules.
- The characterization suggests a divide-and-conquer recognition strategy: compute the modular decomposition, test modules for comparability, and recursively test the quotient, which could make word-representability testing efficient on structured instances despite the general NP-completeness.
- The universal-vertex forcing argument is not specific to word-representable graphs, so the same replacement theorem is likely transferable to other hereditary graph classes closed under induced subgraphs that contain comparability graphs.
- The max formula for lexicographical products indicates that the second factor's permutation-representation number is the controlling parameter, and one might test whether other graph products obey similar max formulas.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies word-representable graphs through modular decomposition. It introduces the operation Ga[M] that replaces a vertex a of G by a module M, and claims a characterization (Theorem 4): Ga[M] is word-representable if and only if G is word-representable and M is a comparability graph. It then applies this to the lexicographical product G[G'] (Theorem 6), to the modular-decomposition characterization (Theorem 8), and to formulas for the representation number R(G) and the permutation-representation number Rp(G) in terms of the quotient and the modules. The abstract advertises a complete answer to the Kitaev–Lozin open problem on lexicographical products.
Significance. If the technical gaps identified below are repaired, the paper would provide a useful structural tool: it reduces word-representability of a decomposable graph to comparability tests on the modules and word-representability of the quotient, and it gives a representation-number formula using permutation-representation numbers. The paper also correctly identifies and corrects a prior error in Kitaev [8], where R(M) should be Rp(M), and Example 1 with the wheel W6 is a valid counterexample to the earlier claim. The proposed polynomial-time non-word-representability test for decomposable graphs with a non-comparability module is a concrete practical consequence. However, the central theorems currently have load-bearing gaps, so the result is not yet publishable in its present form.
major comments (4)
- [§2, Theorem 4] Theorem 4 is false as stated because the proof requires a vertex b in N_G(a), which exists only when G has at least two vertices. For G = K1, the construction gives Ga[M] = M, so the theorem would imply that every word-representable graph is a comparability graph, which fails for M = C5. The statement must add the hypothesis |V(G)| >= 2, equivalently N_G(a) nonempty. This missing hypothesis propagates to Theorem 6 and to the use of Theorem 4 in Lemma 1.
- [§2, Theorem 6] Theorem 6, advertised as the complete answer to the Kitaev–Lozin problem, is false as stated for G = K1: since K1[G'] is isomorphic to G', the claim 'G[G'] word-representable iff G word-representable and G' comparability' would force every word-representable graph to be comparability. The theorem needs either the hypothesis that G has at least two vertices or a separate treatment of the K1 case, where the condition reduces to word-representability of G'.
- [§2, Theorem 3] Theorem 3 is stated without proof, yet its lower bound R(Ga[M]) >= Rp(M) is essential for the representation-number formula in Theorem 8(2) and for the representation-number claim in Theorem 6. The paper cites the related result in [8] and gives a counterexample to the earlier statement with R(M), but it does not supply a proof of the corrected version. Since the representation-number formula is a main contribution, this proof must be provided in the manuscript; a citation alone is insufficient, especially because the cited paper contains the false statement.
- [§2, Lemma 1 and Theorem 8(1)] After the missing hypothesis in Theorem 4 is added, the proof of Lemma 1 must explicitly verify that the replacement vertex a has a neighbor in G'. For a nontrivial module M in a connected decomposable graph, this holds because every proper module in a connected graph has a neighbor outside it; the proof should state this. Without such a statement, the application of Theorem 4 is formally not justified from the current text.
minor comments (5)
- [Abstract] There is a typo in 'word-representab le' in the abstract; it should be 'word-representable'.
- [§2, proof of Theorem 8(1)] The sentence 'it is an word-representable graph' should read 'it is a word-representable graph'.
- [§2, definition of Ga[M]] The definition of Ga[M] should explicitly state that the vertex sets V ∪ {a} and V' are disjoint, otherwise the union V ∪ V' and the edge set are not well-defined in general.
- [§2, Remark 3] Remark 3 says 'replacing each vertex of G by the module G''; strictly, the lexicographical product G[G'] is isomorphic to the iterated replacement operation only when the replacements are made for all vertices, and the isomorphism should be stated explicitly rather than asserted informally.
- [§1, notation] The paper uses the same symbol G' for the second graph in the lexicographical product (Theorem 6) and later for the quotient-replacement graph in Lemma 1; this reuse is confusing and should be adjusted.
Circularity Check
No significant circularity: the modular-decomposition characterization is built on external universal-vertex and modular-decomposition theorems, not on the paper's own conclusions.
full rationale
The derivation chain is not circular. Theorem 4's converse forces M to be a comparability graph by invoking Kitaev–Pyatkin's Theorem 9 [10] on word-representable graphs with a universal vertex, applied to the induced subgraph on V'∪{b}; this is an independent external result and is not equivalent to the theorem being proved. The forward direction uses Kitaev's Theorem 2 [8], and Theorem 8 applies Theorem 4 to the quotient obtained by contracting a non-trivial module, so the comparability of each module is derived rather than assumed. The only self-citations — [15] for Rp(C6)=3 in Example 1 and [16] for the standard prn/dimension fact — are auxiliary and not load-bearing; neither is used to justify the modular-decomposition characterization. There are genuine non-circularity issues worth noting separately: Theorem 3 is stated without proof and is needed for Theorem 8(2), and Theorems 3, 4, and 6 silently require the replaced vertex to have a neighbor, failing for G=K1; these are correctness/rigor gaps, not circular reductions.
Assumptions & free parameters
assumptions (6)
- standard math Every word-representable graph is k-word-representable for some k, and the class is hereditary under induced subgraphs.
- standard math If G is word-representable and M is a comparability graph, then Ga[M] is word-representable, as in Theorem 2 of [8].
- standard math If a graph with a universal vertex is word-representable, then deleting that vertex leaves a comparability graph, and a k-uniform representation forces the remaining graph to be permutationally k-representable, as in Theorem 9 of [10].
- standard math A graph is a comparability graph if and only if all modules in a modular partition and the associated quotient graph are comparability graphs, as in Theorem 1 of [4,14].
- standard math Every graph has a unique maximal modular partition, computable in linear time, from [5,13].
- domain assumption All graphs are finite, simple, and connected.
Cite this review
Pith. "Pith review of Characterization of Word-Representable Graphs using Modular Decomposition." pith.science (2026). https://pith.science/paper/BYBMYAEF
@misc{pith2026241217648,
author = {Pith},
title = {Pith review of: Characterization of Word-Representable Graphs using Modular Decomposition},
year = {2026},
howpublished = {\url{https://pith.science/paper/BYBMYAEF}},
note = {Machine review of arXiv:2412.17648}
}
read the original abstract
In this work, we characterize the class of word-representable graphs with respect to the modular decomposition. Consequently, we determine the representation number of a word-representable graph in terms of the permutation-representation numbers of the modules and the representation number of the associated quotient graph. In this connection, we also obtain a complete answer to the open problem posed by Kitaev and Lozin on the word-representability of the lexicographical product of graphs.
Figures
Reference graph
Works this paper leans on
-
[8]
S. Kitaev. On graphs with representation number 3. J. Autom. Lang. Comb. , 18(2):97–112, 2013
2013
-
[1]
I. Choi, J. Kim, and M. Kim. On operations preserving semi- transitive orientability of graphs. J. Comb. Optim. , 37(4):1351–1366, 2019
work page 2019
-
[2]
T. Gallai. Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hungar. , 18:25– 66, 1967
1967
-
[3]
M. C. Golumbic. The complexity of comparability graph rec ognition and coloring. Computing, 18(3):199–208, 1977
work page 1977
-
[4]
M. C. Golumbic. Algorithmic graph theory and perfect graphs , volume 57 of Annals of Discrete Mathematics . Elsevier Science B.V., Amsterdam, second edition, 2004. 8
work page 2004
-
[5]
M. Habib and C. Paul. A survey of the algorithmic aspects of modular decompo- sition. Computer Science Review , 4(1):41–59, 2010
work page 2010
-
[6]
M. M. Halld´ orsson, S. Kitaev, and A. Pyatkin. Alternatio n graphs. In Graph- theoretic concepts in computer science , volume 6986 of Lecture Notes in Comput. Sci., pages 191–202. Springer, Heidelberg, 2011
work page 2011
-
[7]
M. M. Halld´ orsson, S. Kitaev, and A. Pyatkin. Semi-trans itive orientations and word-representable graphs. Discrete Appl. Math. , 201:164–171, 2016
work page 2016
Show all 17 references
-
[9]
Kitaev and V
S. Kitaev and V. Lozin. Words and graphs . Monographs in Theoretical Computer Science. An EATCS Series. Springer, Cham, 2015
2015
-
[10]
Kitaev and A
S. Kitaev and A. Pyatkin. On representable graphs. J. Autom. Lang. Comb. , 13(1):45–54, 2008
2008
-
[11]
Kitaev and S
S. Kitaev and S. Seif. Word problem of the Perkins semigro up via directed acyclic graphs. Order, 25(3):177–194, 2008
2008
-
[12]
Kitaev and H
S. Kitaev and H. Sun. Human-verifiable proofs in the theor y of word-representable graphs. RAIRO-Theor. Inf. Appl. , 58:9, 2024
2024
-
[13]
R. M. McConnell and J. P. Spinrad. Linear-time modular de composition and efficient transitive orientation of comparability graphs. I n Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Arlingt on, V A, 1994) , pages 536–545. ACM, New York, 1994
1994
-
[14]
R. H. M¨ ohring. Algorithmic aspects of comparability gr aphs and interval graphs. In Graphs and order (Banff, Alta., 1984) , volume 147 of NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci. , pages 41–101. Reidel, Dordrecht, 1985
1984
-
[15]
Mozhui and K
K. Mozhui and K. Krishna. Graphs with permutation-repre sentation number at most three. arXiv:2307.00301, 2023
2023 arXiv
-
[16]
Mozhui and K
K. Mozhui and K. V. Krishna. On the permutation-represen tation number of bipartite graphs using neighborhood graphs. arXiv:2311.13980, 2023
2023 arXiv
-
[17]
Yannakakis
M. Yannakakis. The complexity of the partial order dimen sion problem. SIAM J. Algebraic Discrete Methods , 3(3):351–358, 1982
1982
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.