{"id":"11193d13-1326-422f-b274-252f9bfd4aaf","arxiv_id":"2412.17648","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A graph made by substituting a module into a word-representable graph is word-representable if and only if the module is a comparability graph, yielding a characterization of lexicographic products.","lead":"This paper finds a modular-decomposition rule for word-representable graphs and uses it to settle an open problem about lexicographic products of graphs. The main result says such products are word-representable exactly when the base graph is word-representable and the substituted layer is a comparability graph.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorems 3, 4, and 6 are false as stated for G = K1: the replacement and lexicographic products degenerate to M or G', forcing every word-representable graph to be comparability. A nontriviality hypothesis on the replaced vertex is missing.","rationale":"I read the paper as attempting to prove a modular-decomposition characterization of word-representable graphs and a representation-number formula. The core mechanism is sound: an outside neighbor of the replaced vertex becomes universal to the module, and the known universal-vertex theorem forces the module to be comparability. Thus the main modular-decomposition theorem is not the source of the difficulty. The load-bearing flaw is the missing nontriviality hypothesis in Theorems 3, 4, and 6. The one-vertex case gives a concrete counterexample to the lexicographic-product claim, which is a headline contribution of the paper, and it also breaks the representation-number formula. The reader identified exactly this issue, and I agree. In addition, Theorem 3 is asserted without proof; a revised version must not only add the hypothesis but also prove the lower bound R(Ga[M]) >= Rp(M), since that bound is not immediate from induced subgraphs. These are local, fixable problems rather than evidence that the main theorem is false, so the conditional verdict is appropriate.","tokens_in":6427,"tokens_out":15266,"duration_ms":152318,"concrete_test":"Verify Theorem 6 at G = K1 and G' = C5. Since K1[C5] is isomorphic to C5 and C5 is word-representable, the stated biconditional would force C5 to be a comparability graph. But C5 is an odd cycle and is not a comparability graph. This single instance refutes the theorem as written. After adding the hypothesis |V(G)| >= 2, also check the corrected statement on all connected graphs with at most five vertices by brute-force word search, to confirm that no further degeneracies arise.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The weakest point is the proof of Theorem 4, which chooses b in N_G(a) and makes b adjacent to all of M. This requires a to have at least one neighbor. Since the paper assumes only connectedness, the excluded case is exactly G = K1, and K1 is a connected graph. When G = K1, V is empty and Ga[M] = M. Theorem 4 then asserts that M is word-representable iff M is a comparability graph, which fails for M = C5: C5 is word-representable but not a comparability graph. The same degeneracy propagates to Theorem 3: for G = K1 and M = C6, R(G) = 1, Rp(M) = 3, and Ga[M] = C6, so the claimed equality R(Ga[M]) = max{1,3} = 3 contradicts the known value R(C6) = 2. It also invalidates Theorem 6, which is advertised as a complete answer to the Kitaev-Lozin open problem, because K1[C5] is isomorphic to C5. The needed extra hypothesis is |V(G)| >= 2, equivalently N_G(a) is nonempty, for the replacement operation. Theorem 8 itself is probably safe, because in a decomposable connected graph every nontrivial module has a neighbor outside the module. Separately, Theorem 3 is stated without proof, and its lower bound R(Ga[M]) >= Rp(M) is essential for the representation-number formula in Theorem 8(2); even after excluding K1, that proof must be supplied.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":6766,"tokens_out":4004,"duration_ms":38396,"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":[{"comment":"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.","section":"§2, Theorem 4"},{"comment":"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'.","section":"§2, Theorem 6"},{"comment":"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.","section":"§2, Theorem 3"},{"comment":"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.","section":"§2, Lemma 1 and Theorem 8(1)"}],"minor_comments":[{"comment":"There is a typo in 'word-representab le' in the abstract; it should be 'word-representable'.","section":"Abstract"},{"comment":"The sentence 'it is an word-representable graph' should read 'it is a word-representable graph'.","section":"§2, proof of Theorem 8(1)"},{"comment":"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.","section":"§2, definition of Ga[M]"},{"comment":"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.","section":"§2, Remark 3"},{"comment":"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.","section":"§1, notation"}],"recommendation":"major_revision","confidential_remarks":"The technical core is largely an application of known results, and the novelty lies in the modular-decomposition formulation and the representation-number formulas. The missing K1 hypothesis is easily fixed, and the unproved Theorem 3 is the more serious gap; the authors should be asked to supply a full proof of Theorem 3 or to cite a published source that contains it. Given the paper's reliance on prior theorems, the editor may also wish to verify that the contribution is sufficient for the target journal after the revisions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Kitaev and Lozin's open problem gets a credible answer here. The paper correctly distinguishes representation number from permutation-representation number and fixes a wrong statement in Kitaev's earlier work (Example 1). The modular-decomposition characterization, Theorem 8, is the first one I know for word-representable graphs, and the lexicographic-product result is new. This is worth engaging with.\n\nThe soft spots are real but localized. Theorems 3, 4, and 6 are stated without the hypothesis that the replaced vertex has a neighbor. When G=K1, the construction degenerates: Ga[M]=M and K1[G']=G'. Then Theorem 4 says M is word-representable iff it is comparability, which is false for C5. Theorem 3 similarly breaks for C6, giving R=3 instead of the known R=2. This is a one-line fix — require |V(G)|>=2 or N_G(a) nonempty — and it does not touch Theorem 8, since a decomposable graph with a nontrivial module always has vertices outside the module and crossing edges. So the central characterization is probably safe.\n\nThe bigger issue is Theorem 3. It is stated without proof, and the lower bound R(Ga[M]) >= Rp(M) is not obvious. The upper bound can probably be obtained by replacing copies of a in a k-uniform word with permutations for M, but the lower bound needs an argument. Since Theorem 8(2) leans on this formula, the proof really needs to appear. Without it, the representation-number part is unverified.\n\nThe citation pattern looks fine; the self-citations are for auxiliary facts, and the paper is transparent about the error it corrects. I did not see circularity.\n\nBottom line: this is a paper for the word-representable graph community. With the K1 case excluded and a proof of Theorem 3 added, it would be a solid contribution. Send it to a serious referee, with instructions to check the gap cases.","headline":"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.","tokens_in":7263,"tokens_out":3707,"would_cite":false,"duration_ms":34470,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C62","05C75","05C76"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["word-representable graphs","modular decomposition","comparability graphs","representation number","permutation-representation number","lexicographical product","quotient graph"],"falsifier":"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.","tokens_in":6237,"feed_emoji":"🧩","tokens_out":11073,"duration_ms":85270,"temperature":0.7,"pith_summary":"This paper establishes a structural characterization of word-representable graphs using modular decomposition. Its central result is that replacing a vertex of a graph G by a module M yields a word-representable graph exactly when G is word-representable and M is a comparability graph, meaning a graph whose edges admit a transitive orientation. From this local replacement theorem it settles the open problem about lexicographical products: G[G'] is word-representable if and only if G is word-representable and G' is a comparability graph. For a decomposable graph, word-representability reduces to checking that every module in a maximal modular partition is a comparability graph and that the associated quotient graph is word-representable. The representation number then equals the maximum of the quotient's representation number and the permutation-representation numbers of the modules.","feed_headline":"Word-representable graphs characterized via modular decomposition","feed_subtitle":"Replacing a vertex by a module keeps a graph word-representable exactly when the module is a comparability graph.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Provides the equivalence between word-representability and k-uniform word-representability and the theorem used to force a module to be a comparability graph from a universal vertex.","marker":"[10]"},{"why":"Establishes that a graph is a comparability graph exactly when it is permutationally representable, linking prn to comparability.","marker":"[11]"},{"why":"Supplies the sufficient condition that replacing a vertex with a comparability module preserves word-representability, the forward direction of Theorem 4.","marker":"[8]"},{"why":"The monograph that poses the open lexicographical product problem and provides background facts and examples used in the paper.","marker":"[9]"},{"why":"Demonstrates that word-representable graphs are not closed under lexicographical product, motivating the exact characterization of Theorem 6.","marker":"[1]"},{"why":"Gives the linear-time modular decomposition algorithm that supports the polynomial-time test in the concluding remarks.","marker":"[13]"},{"why":"States the modular-decomposition characterization of comparability graphs used for the comparability case of the main theorem.","marker":"[4]"}],"fun_headline_variants":["Word-representable graphs pinned down by modular decomposition","Modular decomposition: key to word-representable graph characterization","Replacing a vertex with a comparability graph preserves word-representability","Modular decomposition reveals exact condition for word-representable graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Word-representable graphs pinned down by modular decomposition","Modular decomposition: key to word-representable graph characterization","Replacing a vertex with a comparability graph preserves word-representability","Modular decomposition reveals exact condition for word-representable graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000733,"raw_usage":{"total_tokens":3199,"prompt_tokens":783,"completion_tokens":2416,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":399,"completion_tokens_details":{"reasoning_tokens":2349}},"tokens_in":399,"tokens_out":2416,"duration_ms":15660,"temperature":1.0,"reasoning_tokens":2349,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T05:19:10.614391+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Demonstrates that word-representable graphs are not closed under lexicographical product, motivating the exact characterization of Theorem 6."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the linear-time modular decomposition algorithm that supports the polynomial-time test in the concluding remarks."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"States the modular-decomposition characterization of comparability graphs used for the comparability case of the main theorem."}],"review_version":1}