Representation Number of Word-Representable Split Graphs

Khyodeno Mozhui; K. V. Krishna; Tithi Dwary

REVIEW 2 major objections 4 minor 2 cited by

Representation Number of Word-Representable Split Graphs

T0 review · 2 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every word-representable split graph has a 3-uniform word representative.

desk verdict A credible and likely correct resolution of R(G)≤3 for word-representable split graphs, but the exact-3 characterization for comparability graphs leans on an unpublished preprint by the same authors. read the letter →

arxiv 2502.00872 v2 pith:O3YZZ3LJ submitted 2025-02-02 math.CO cs.DM

Tithi Dwary , Khyodeno Mozhui , K. V. Krishna This is my paper · ORCID

classification math.COcs.DM

keywords word-representablegraphsrepresentationnumbersplitcomparability3-uniformwordscircleforbiddeninducedsubgraphsalgorithmicwordconstruction

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

A split graph is a graph whose vertices can be split into a clique, where every pair is adjacent, and an independent set, where no edges appear. A graph is word-representable when some finite word over its vertices has the property that two letters alternate exactly when the two vertices are adjacent. This paper proves that every word-representable split graph is 3-word-representable: there is always a word in which each vertex appears exactly three times. The proof is constructive, producing the word by a fixed algorithm from the clique labeling supplied by an earlier characterization. The paper also characterizes exactly when three appearances are necessary: among word-representable split graphs, this happens precisely when the graph contains one of the listed induced subgraphs, and among split comparability graphs only when it contains $F_0$ or $F_1(5)$.

What carries the argument

The machine that carries the argument is Algorithm 1's word $w=p_1(p_1|_B)^R p_2 p_3$, where $p_1$ and $p_2$ are permutations on the whole vertex set, $p_3$ is a permutation on $C\cup A$ only, and the $B$-vertices receive their third occurrence in the reversed subword $(p_1|_B)^R$. Because every vertex appears in three of these four factors, $w$ is 3-uniform. The insertion rules place each independent vertex $a$ beside the boundary of its neighborhood in the ordered clique: $A$-vertices go next to the right end of their left interval in $p_1$ and the left end of their right interval in $p_2$; $B$-vertices go next to the two ends of their single interval in $p_1$ and $p_2$; and $p_3$ is built by reversing the $A$-order after a pivot $d$, which Remark 1 guarantees lies between all left ends and all right ends of $A$-neighborhoods. These placements reduce the alternation checks in Lemmas 1–4 to the interval order.

What would settle it

Take any split graph whose clique labeling satisfies the three conditions of Theorem 3, run Algorithm 1, and check the alternation pattern of the resulting word against the graph's adjacency matrix; a single edge whose two letters fail to alternate, or a single non-edge whose two letters do alternate, would refute Theorem 5. An exhaustive search over small split graphs computing their representation number would also settle the bound: finding one word-representable split graph with representation number 4 is a counterexample.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is an upper bound with a witness: every word-representable split graph $G=(I\cup C,E)$ has $R(G)\le 3$. After labeling the clique $C$ as $1,\dots,k$ according to Theorem 3, each independent vertex has a neighborhood of one of two shapes, a single interval $[l,r]$ (collected in $B$) or two end intervals $[1,m]\cup[n,k]$ (collected in $A$). Algorithm 1 constructs three permutations $p_1,p_2,p_3$ and returns the 3-uniform word $w=p_1(p_1|_B)^R p_2 p_3$. Lemmas 2–4 check every pair type: clique–clique edges alternate, independent-to-clique adjacencies alternate, and all non-edges fail to alternate, so $w$ represents $G$. Theorem 6 then characterizes $R(G)=3$ by the presence of an induced subgraph from the family $\mathcal{C}_3$, and Theorem 8 restricts that characterization for split comparability graphs to $F_0$ and $F_1(5)$.

Load-bearing premise

The proof depends on an earlier theorem, taken as given, that every word-representable split graph has its clique vertices ordered so that each independent vertex's neighbors form either one consecutive block or two blocks at the two ends, with three compatibility rules between these blocks, and that such an ordering can be found in polynomial time. If that theorem had a hidden extra condition or the ordering procedure could fail, the word constructed here would not be guaranteed to represent every word-representable split graph.

Editorial extensions

If this is right

Every word-representable split graph has a concrete 3-uniform representative, so the representation number of the entire class is bounded by 3.
A word-representable split graph has representation number exactly 3 precisely when it contains an induced copy of $F_0$, an even $k$-sun ($k\ge 4$), or $F_1(k)$/$F_2(k)$ for odd $k\ge 5$; otherwise its representation number is at most 2.
For split comparability graphs, representation number 3 is equivalent to containing $F_0$ or $F_1(5)$ as an induced subgraph.
Because the upper-bound proof is an algorithm rather than an existence argument, the representing word is produced directly from the clique labeling.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A complexity corollary the paper does not state: since word-representable split graphs are recognizable in polynomial time and Algorithm 1 supplies a 3-uniform word, deciding whether a split graph has representation number at most 3 is polynomial for this class, even though the general problem is NP-complete.
The exact-3 characterization is expressed through the family $\mathcal{C}_3$ sitting inside the larger circle-graph forbidden family $\mathcal{C}$; the paper's conclusion suggests that shrinking this to a list of minimal forbidden induced subgraphs is the next step, and would make the $R(G)=3$ test purely structural.
The same concatenation pattern, three factors with the middle factor reversed over one type of independent vertex, may transfer to any graph class admitting an interval-neighborhood labeling of the same two-shape form, not only split graphs.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

First thing you should know: this paper proves that every word-representable split graph has representation number at most 3, and it gives an explicit algorithm that constructs a 3-uniform representing word. I read the construction carefully and the proof of Theorem 5 holds up. The systematic case analysis in Lemmas 2–4 checks every adjacency type and I didn't find a gap. The main theorem is genuinely new — earlier work only bounded the permutation-representation number of split comparability graphs, not the representation number of all word-representable split graphs.

What's actually good: Algorithm 1 is a real contribution. It uses the interval-neighborhood labeling of the clique from Kitaev–Long–Ma–Wu / Kitaev–Pyatkin and builds three permutations that, when concatenated, represent the graph. The proof that the word is 3-uniform and that alternation matches adjacency is careful. The exact-3 characterization for word-representable split graphs (Theorem 6) is also new, and the forbidden family C3 is explicitly described and mostly verified. The paper is clearly written and self-contained except for its external dependencies.

Soft spots, in proportion to how soft they are. The main load-bearing step is Theorem 3, the known characterization of word-representable split graphs by clique labelings. The paper cites it from [15,18] and uses it to define the sets A and B and to justify every lemma in Section 3. That's legitimate — the result is published — but the current proof is entirely contingent on it. If that theorem had a hidden condition, the construction would fail. I've no reason to doubt it, but I'd expect the paper to state the dependence more forthrightly. The bigger issue is Theorem 4 from the authors' own preprint [4], used to identify F1(5) as a comparability graph in Theorem 7. The characterization of split comparability graphs with representation number 3 is thus contingent on an unrefereed result. That needs to be fixed: either include a proof of Theorem 4 or drop it if a published version exists. There is also a minor slip in Lemma 1: the subword m_adn_a is impossible when m_a = d, since p3 is a permutation at that point and has only one copy of d. The intended result still follows after the line-18 replacement, so it's easily repairable, but it should be corrected.

Bottom line: this is a worthwhile paper for anyone working on word-representable graphs. The core result appears correct and the algorithmic construction is a nice addition. It deserves a serious referee and, with minor revisions addressing the preprint dependency and the Lemma 1 slip, I'd be happy to see it published.

Referee Report

2 major / 4 minor

Summary. The paper studies word-representable split graphs. Its main result is Theorem 5: every word-representable split graph has representation number at most three. The proof takes an external labeling characterization (Theorem 3, attributed to [15,18]), partitions the independent vertices into classes A and B according to whether their clique-neighborhoods are two-ended or interval, and gives Algorithm 1 that outputs a 3-uniform word w = p1(p1|B)^R p2 p3. Lemmas 1-4 verify alternation for adjacent and non-adjacent pairs, and Theorem 5 assembles these checks. The paper then characterizes the subclass with representation number exactly three (Theorem 6) as those containing an induced graph from the family C3, and, for split comparability graphs (Theorem 8), as those containing F0 or F1(5).

Significance. If correct, the paper resolves the open question of the representation number of word-representable split graphs, proving a uniform upper bound of 3 and identifying the exact induced-subgraph obstructions to representation number 3. The construction is explicit and algorithmic, and the alternation lemmas are self-contained case analyses once the external labeling theorem is granted. The paper also makes good use of the published forbidden-subgraph characterizations of split circle and split permutation graphs. The main caveats are an edge case in the interval notation that the proof does not handle, and a dependence on an unpublished companion preprint for part of the exact-three characterization. Apart from these points, I found no internal derivation gap in the central R(G) ≤ 3 argument.

major comments (2)

[Section 2, Theorem 3 and Section 3, Algorithm 1] As stated, Theorem 3 does not cover independent vertices with N(a) = ∅, because the notation [a,b] is defined only for a ≤ b and neither [l,r] nor [1,m] ∪ [n,k] can be empty under that convention. Such vertices occur in word-representable split graphs (for example, K2 ∪ K1 with the isolated vertex in I), so the A/B partition and Algorithm 1 do not apply to all allowed inputs. Please add an explicit reduction: an isolated independent vertex can be represented by appending its three occurrences consecutively to the constructed word, or extend the interval notation and adjust Algorithm 1 accordingly. This is a local fix, but it is load-bearing for Theorem 5 as written.
[Section 3.2, Theorems 7 and 8] The proof that F1(5) is a comparability graph invokes Theorem 4, which is cited only as the authors' preprint [4] and is not proved in this manuscript. Since Theorem 8 is a stated characterization of the paper, this is a load-bearing external dependence. Please either prove Theorem 4 (or the specific labeling conditions used for F1(5)) directly in the paper, or cite a peer-reviewed source for it.

minor comments (4)

[Lemma 1, proof] The displayed subword m_a d n_a is not actually a subword of p3 when m_a = d, because p3 contains only one copy of d. The intended conclusion m_a a n_a ≪ p3 is still correct after line 18, but the notation should be clarified, for example by writing m_a ... d ... n_a and explaining that the middle position may coincide with m_a.
[Section 3, after Algorithm 1] The paper implicitly uses that w is 3-uniform, but this is never stated as a separate observation. It would help to say explicitly: C-vertices occur in p1, p2, p3; B-vertices occur in p1, (p1|B)^R, p2; and A-vertices occur in p1, p2, p3.
[Lemma 10, Case 1] The backward labeling statement 'vertices c_{k−3},...,c_{k−m} are labeled m−1,...,2' is not meaningful when m = 1, since m−1 = 0 is not a label. The contradiction can still be obtained for m = 1, but the case needs a separate sentence or a cleaner index convention.
[Theorem 6, proof] The converse direction uses the fact that an induced non-circle subgraph makes the whole graph non-circle; this is the heredity of circle graphs and should be stated explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular step found: the R(G) ≤ 3 proof constructs an explicit 3-uniform word from the external interval-neighborhood characterization and verifies alternation directly.

full rationale

The central claim, Theorem 5, is not circular. Algorithm 1 takes the external characterization of word-representable split graphs (Theorem 3, from [15,18]) as its input, constructs the word p1(p1|B)^R p2 p3, and Lemmas 2–4 verify directly that alternation in that word coincides with adjacency. The proof does not assume the conclusion R(G) ≤ 3, and no fitted parameter or defined-in-terms-of-target quantity is involved. The same-author preprint [4] is cited for Theorem 4 and used only in the auxiliary split-comparability characterization (Theorem 7), not in the derivation of the headline bound; this is a self-citation that is unproved in the present paper, but it is not a reduction of the central claim to its inputs. External results from [1,8,10,15,17,18] support the auxiliary lemmas, so the paper is self-contained against external benchmarks. A minor non-circular proof defect appears in Lemma 1: the displayed subword m_ad_n_a ≪ p3 is impossible when m_a = d because p3 contains d only once; however, the intended m_a a n_a subword follows from the line-18 replacement d ↦ d(p1|A)^R, so this is a correctable typo rather than a circular step.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The main theorem rests on prior structural characterizations rather than on fitted numerical parameters. No constants are tuned to data. The most fragile input is the authors' unpublished preprint [4], but it affects only the comparability subcharacterization, not the R(G) ≤ 3 construction.

assumptions (5)

domain assumption Theorem 3 characterization of word-representable split graphs by interval labelings (Kitaev, Long, Ma, Wu 2021; Kitaev and Pyatkin 2024)
Invoked at the start of Section 3 and used in every lemma of the construction; the paper cites [15,18] instead of proving it.
domain assumption Word-representable graphs with representation number at most 2 are exactly circle graphs (Halldorsson, Kitaev, Pyatkin 2011)
Used in Theorem 6 to convert R(G)=3 into non-circleness and then apply the split-graph circle characterization.
domain assumption Forbidden induced subgraph characterization of circle graphs within split graphs (Bonomo-Braberman et al. 2022, corrected by Pardal)
Theorem 1(ii) is the bridge that produces the family C in Theorem 6; the exactly-3 characterization inherits its correctness.
domain assumption Theorem 4 from the authors' preprint [4] characterizes transitively orientable split graphs by the five labeling conditions
Used to verify F1(5) is a comparability graph in Theorem 7; this is the least independently verified input since [4] is an unpublished same-author preprint.
domain assumption Split graph comparability characterization by absence of B1, B2, B3 (Golumbic)
Used in Lemmas 8 and 10-14 to decide which graphs in C are comparability graphs.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Representation Number of Word-Representable Split Graphs." pith.science (2026). https://pith.science/paper/O3YZZ3LJ

@misc{pith2026250200872,
  author       = {Pith},
  title        = {Pith review of: Representation Number of Word-Representable Split Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/O3YZZ3LJ}},
  note         = {Machine review of arXiv:2502.00872}
}

read the original abstract

A split graph is a graph whose vertex set can be partitioned into a clique and an independent set. The word-representability of split graphs was studied in a series of papers in the literature, and the class of word-representable split graphs was characterized through semi-transitive orientation. Nonetheless, the representation number of this class of graphs is still not known. In general, determining the representation number of a word-representable graph is an NP-complete problem. In this work, through an algorithmic procedure, we show that the representation number of the class of word-representable split graphs is at most three. Further, we characterize the class of word-representable split graphs as well as the class of split comparability graphs which have representation number exactly three.

Figures

Figures reproduced from arXiv: 2502.00872 by the authors.

**Figure 1.** The family of graphs B 2 Split Graphs A graph G = (V, E) is a split graph if the vertex set V can be partitioned as I ∪C, where I induces an independent set, and C induces a clique in G. In what follows, we denote G = (I ∪ C, E), where C is inclusion wise maximal, i.e., no vertices of I is adjacent to all vertices of C. Foldes and Hammer introduced the class of split graphs and characterized them as (2K2, C4, C5)-fr… view at source ↗

**Figure 2.** The family C of split graphs done in polynomial time. The following characterization of word-representable split graphs is a key tool for our work. In what follows, for any two integers a ≤ b, we denote the set of integers {a, a + 1, . . . , b} by [a, b] [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

On the Conjecture of the Representation Number of Bipartite Graphs
math.CO 2025-06 conditional novelty 7.0 of 10

Every bipartite graph is (1+ceil(m/2))-representable, improving to ceil(m/2) when the smaller part has odd size, settling the Glen et al. conjecture except for equal-even bipartitions.
Characterization of Split Comparability Graphs
math.CO 2025-04 conditional novelty 5.0 of 10

Split comparability graphs are exactly the split graphs whose clique can be labeled so that each independent-set vertex sees a prefix, a suffix, or a two-ended interval, and every such graph has permutation-representa...

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages · cited by 2 Pith papers

[4]

Dwary, K

T. Dwary, K. Mozhui, and K. V. Krishna. Characterization o f split comparability graphs. Preprint, 2025

work page 2025
[1]

Bonomo-Braberman, G

F. Bonomo-Braberman, G. Dur´ an, N. Pardal, and M. D. Safe. Forbidden in- duced subgraph characterization of circle graphs within sp lit graphs. Discrete Appl. Math. , 323:43–75, 2022

work page 2022
[2]

Broere and H

B. Broere and H. Zantema. The k-dimensional cube is k-representable. J. Autom. Lang. Comb. , 24(1):3–12, 2019

work page 2019
[3]

H. Z. Q. Chen, S. Kitaev, and A. Saito. Representing split g raphs by words. Discuss. Math. Graph Theory , 42(4):1263–1280, 2022

work page 2022
[5]

Foldes and P

S. Foldes and P. L. Hammer. Split graphs. In Proceedings of the Eighth Southeast- ern Conference on Combinatorics, Graph Theory and Computin g (Louisiana State Univ., Baton Rouge, La., 1977) , Congress. Numer., pages 311–315, 1977

work page 1977
[6]

T. Gallai. Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hungar. , 18:25– 66, 1967

work page 1967
[7]

M. Glen, S. Kitaev, and A. Pyatkin. On the representation n umber of a crown graph. Discrete Appl. Math. , 244:89–93, 2018

work page 2018
[8]

M. C. Golumbic. Algorithmic graph theory and perfect graphs , volume 57 of Annals of Discrete Mathematics . Elsevier Science B.V., Amsterdam, second edition, 2004

work page 2004

Show all 23 references

[9]

Guenver and J.-X

G.-B. Guenver and J.-X. Rampon. Split orders. Discrete Math., 276(1-3):249–267, 2004

2004
[10]

M. M. Halld´ orsson, S. Kitaev, and A. Pyatkin. Alternati on graphs. In Graph- theoretic concepts in computer science , volume 6986 of Lecture Notes in Comput. Sci., pages 191–202. Springer, Heidelberg, 2011

2011
[11]

M. M. Halld´ orsson, S. Kitaev, and A. Pyatkin. Semi-tran sitive orientations and word-representable graphs. Discrete Appl. Math. , 201:164–171, 2016

2016
[12]

Iamthong

K. Iamthong. Word-representability of split graphs gen erated by morphisms. Dis- crete Appl. Math. , 314:284–303, 2022

2022
[13]

Iamthong and S

K. Iamthong and S. Kitaev. Semi-transitivity of directe d split graphs generated by morphisms. J. Comb. , 14(1):111–138, 2023. 14

2023
[14]

S. Kitaev. On graphs with representation number 3. J. Autom. Lang. Comb. , 18(2):97–112, 2013

2013
[15]

Kitaev, Y

S. Kitaev, Y. Long, J. Ma, and H. Wu. Word-representabili ty of split graphs. J. Comb., 12(4):725–746, 2021

2021
[16]

Kitaev and V

S. Kitaev and V. Lozin. Words and graphs . Monographs in Theoretical Computer Science. An EATCS Series. Springer, Cham, 2015

2015
[17]

Kitaev and A

S. Kitaev and A. Pyatkin. On representable graphs. J. Autom. Lang. Comb. , 13(1):45–54, 2008

2008
[18]

Kitaev and A

S. Kitaev and A. Pyatkin. On semi-transitive orientabil ity of split graphs. Inform. Process. Lett., 184:Paper No. 106435, 4, 2024

2024
[19]

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
[20]

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
[21]

Mozhui and K

K. Mozhui and K. V. Krishna. Words for the graphs with perm utation- representation number at most three. arXiv:2307.00301, 2023

2023 arXiv
[22]

N. Pardal. Structural characterization of some problems on circle and interval graphs. PhD thesis, University of Buenos Aires, Argentina, 2020

2020
[23]

Yannakakis

M. Yannakakis. The complexity of the partial order dimen sion problem. SIAM J. Algebraic Discrete Methods , 3(3):351–358, 1982

1982

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.

[1] [4]

Dwary, K

T. Dwary, K. Mozhui, and K. V. Krishna. Characterization o f split comparability graphs. Preprint, 2025

work page 2025

[2] [1]

Bonomo-Braberman, G

F. Bonomo-Braberman, G. Dur´ an, N. Pardal, and M. D. Safe. Forbidden in- duced subgraph characterization of circle graphs within sp lit graphs. Discrete Appl. Math. , 323:43–75, 2022

work page 2022

[3] [2]

Broere and H

B. Broere and H. Zantema. The k-dimensional cube is k-representable. J. Autom. Lang. Comb. , 24(1):3–12, 2019

work page 2019

[4] [3]

H. Z. Q. Chen, S. Kitaev, and A. Saito. Representing split g raphs by words. Discuss. Math. Graph Theory , 42(4):1263–1280, 2022

work page 2022

[5] [5]

Foldes and P

S. Foldes and P. L. Hammer. Split graphs. In Proceedings of the Eighth Southeast- ern Conference on Combinatorics, Graph Theory and Computin g (Louisiana State Univ., Baton Rouge, La., 1977) , Congress. Numer., pages 311–315, 1977

work page 1977

[6] [6]

T. Gallai. Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hungar. , 18:25– 66, 1967

work page 1967

[7] [7]

M. Glen, S. Kitaev, and A. Pyatkin. On the representation n umber of a crown graph. Discrete Appl. Math. , 244:89–93, 2018

work page 2018

[8] [8]

M. C. Golumbic. Algorithmic graph theory and perfect graphs , volume 57 of Annals of Discrete Mathematics . Elsevier Science B.V., Amsterdam, second edition, 2004

work page 2004