Characterization of Split Comparability Graphs

Khyodeno Mozhui; K. V. Krishna; Tithi Dwary

REVIEW 3 major objections 4 minor 14 references

Characterization of Split Comparability Graphs

T0 review · 3 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

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

Pith's one-line read Three permutations represent every split comparability graph

desk verdict Useful labeling characterization and B4 equality result, but the main upper bound's proof defers all A1 cases to an unpublished companion preprint; worth reviewing with that condition attached. read the letter →

arxiv 2504.19167 v1 pith:NM7SH3OJ submitted 2025-04-27 math.CO cs.DM

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

classification math.COcs.DM MSC 05C6205C7506A07

keywords splitgraphscomparabilityword-representablepermutation-representationnumbertransitiveorientationordersposetdimension

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

This paper establishes a vertex-labelling characterization of split comparability graphs and uses it to show that every such graph is encoded by a word that is the concatenation of three permutations, with each vertex appearing once in each permutation. In the labelling, the clique vertices are ordered 1 to k, and every independent vertex has one of three neighbourhood shapes: a prefix of the clique, a suffix of the clique, or two separated end-blocks. From this labelling, an explicit algorithm builds the three-permutation word, so the permutation-representation number of every split comparability graph is at most 3. The number is exactly 3 precisely when the graph contains the small forbidden induced subgraph B4. Since the permutation-representation number of a comparability graph equals the dimension of its induced poset, the paper re-derives the known order-theory fact that every split order has dimension at most 3, with the bound tight.

What carries the argument

The load-bearing object is the labelling of the clique $C$ by $1, \ldots, k$, which divides the independent set into three classes: $A_1$ with neighbourhood $[1,m] \cup [n,k]$, $A_2$ with neighbourhood $[1,r]$, and $A_3$ with neighbourhood $[l,k]$. Algorithm 1 uses this labelling to insert each independent vertex into three initially identical permutations $12\cdots k$, choosing insertion positions so that alternation in the final word $q_1q_2q_3$ matches adjacency exactly. The four inequalities of Theorem 5 enforce the order of those insertions, and the resulting word is 3-uniform, so it is a permutation representation.

What would settle it

Run Algorithm 1 on a split comparability graph whose clique labels make some independent vertex adjacent to both the first few and last few clique vertices, and inspect the restricted word for that vertex together with each clique vertex: a single adjacent pair that fails to alternate, or a non-adjacent pair that alternates, would refute the companion step on which Lemmas 3--5 rely.

Watch

Extended reading notes

Core claim

Theorem 5 states that a split graph $G = (I \cup C, E)$ is transitively orientable if and only if its clique vertices can be labelled $1, \ldots, k$ so that independent vertices have neighbourhoods of one of three forms, $[1,m] \cup [n,k]$, $[1,r]$, or $[l,k]$, and the cross-inequalities (ii)--(v) hold. Using that labelling, Algorithm 1 constructs three permutations $q_1, q_2, q_3$ on $V$ and returns the word $q_1q_2q_3$, which is 3-uniform and is proved to represent $G$. Theorem 6 then asserts that $R_p(G) \le 3$, with equality if and only if $G$ contains $B_4$ as an induced subgraph. Corollary 1 restates this as: every split order has dimension at most 3, and the bound is tight.

Load-bearing premise

The construction's correctness for independent vertices whose neighbourhood consists of two separated blocks of the clique is not proved in this paper; it rests entirely on an unpublished companion paper, so if that companion step fails, the bound $R_p(G) \le 3$ is unproved for those vertices.

Editorial extensions

If this is right

For every split comparability graph, $R_p(G) \le 3$; the constructed word is 3-uniform and permutationally represents the graph.
A split comparability graph with no induced $B_4$ is a permutation graph, so $R_p(G) \le 2$; the bound 3 is forced exactly by $B_4$.
The dimension of every induced poset of a split comparability graph is at most 3, and the bound is tight, giving an alternative proof of the split-order dimension theorem.
The labelling of Theorem 5 turns transitivity into four inequalities on neighbourhoods, so the three-permutation word can be read off directly from the clique labelling rather than from an arbitrary transitive orientation.

Reading between the lines

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

If the companion construction is supplied self-contained, the same labelling likely yields a linear-time construction of the three-permutation word, because each vertex is inserted at a fixed position determined by its neighbourhood endpoints.
The $B_4$ dichotomy gives a finite forbidden-subgraph test for whether a split comparability graph is a permutation graph: checking for induced $B_4$ would decide $R_p = 3$ versus $R_p \le 2$.
Because $R_p$ equals poset dimension for comparability graphs, the three-permutation bound might transfer to other hereditary graph classes whose transitive orientations can be normalized so that every vertex's neighbourhood is a union of at most two intervals on a fixed ordering.

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

Short version: this is a decent, honest subfield paper. The genuinely new content is the labeling characterization in Theorem 5 and the equality certificate in Theorem 6 saying Rp(G)=3 exactly when B4 appears as an induced subgraph. The headline bound Rp(G)<=3 is not new: via the prn/dimension equivalence from [13], it is the known result that split orders have dimension at most three. What the paper adds is a direct word construction and a concrete equality statement, so the contribution is modest but real.

The paper does some things well. Theorem 5 is self-contained, and I checked the converse direction: the orientation D is built by explicit cases, and the claims that no A3/A2/A1 vertex can appear as left or right endpoint of a nontransitive triple are internally consistent. Lemma 2 is a neat use of transitivity. The proof of the B4 half of Theorem 6 is short and follows from known split permutation graph results once the upper bound is in place. Algorithm 1 is concrete enough to implement.

The soft spots are real. First and largest: the A1 cases of Lemmas 3, 4, and 5 are not proved in this paper. Remark 3 asserts that the set A in the companion preprint [2] is identical to A1 and the insertion rules are the same, but [2] is unpublished and the reviewer cannot check that identity. Since every edge and non-edge involving an A1 vertex is justified by that transfer, the correctness proof of the word construction is not self-contained. That is a genuine refereeing problem, not a style complaint. Second, Algorithm 1 does not specify the iteration order for 'for a in I'. If two A1 vertices have the same m_a or n_a, the order changes placements, and this paper does not discuss those tie cases; the deferred argument from [2] would have to cover them. Third, [2] and [13] are both self-citations to preprints. That does not make them wrong, but it does mean an editor should ask for those dependencies to be made available or fully incorporated.

Overall, I agree with the conditional verdict. The theorem probably holds—it matches the known dimension result—and the new characterization is useful for people working on word-representable graphs and prn. I would send this to peer review with a request that the A1 argument be made checkable. If I needed the B4 characterization, I would cite it.

Referee Report

3 major / 4 minor

Summary. The paper studies split comparability graphs, i.e., split graphs that admit a transitive orientation. Its main results are (1) a characterization of split comparability graphs in terms of a labeling of the clique vertices (Theorem 5), and (2) an algorithmic proof that every split comparability graph has permutation-representation number at most three (Theorem 6), with equality three exactly when the graph contains B4 as an induced subgraph. The algorithm constructs a word that is a concatenation of three permutations, each a permutation on the vertex set, and the proof of correctness is organized into Lemmas 3-5 establishing alternation and non-alternation properties. The paper also derives, via a known equivalence between permutation-representation number and poset dimension, an alternative proof that split orders have dimension at most three (Corollary 1).

Significance. If the proof can be made fully self-contained, the paper gives a clean labeling characterization of split comparability graphs and a constructive upper bound of three on their permutation-representation number, together with an exact characterization of when the bound is attained. The constructive algorithm is concrete and the converse direction of Theorem 6 rests on established published results. The main caveat is that the correctness proof for a whole class of independent vertices, A1, is deferred to an unpublished companion preprint by the same authors; until that transfer is verified, the central upper-bound claim is not checkable from the manuscript alone.

major comments (3)

[Section 4, Lemma 3 Case 1, Lemma 4 Case 1, Lemma 5 Case 1, and Remark 3] The proof that vertices in A1 have the required alternation behavior is not contained in this paper. For adjacent C-A1 pairs, non-adjacent C-A1 pairs, and A1-A1 pairs, the proof simply invokes Remark 3 and 'Case 1' of the corresponding lemma in the same authors' unpublished preprint [2]. Because A1 is one of the three classes in the partition I = A1 ∪ A2 ∪ A3, every edge and non-edge incident with an A1 vertex is justified only by this external reference. This is load-bearing for Theorem 6: without a verified proof of these cases, the claim Rp(G) ≤ 3 is unsupported for graphs with nonempty A1. The authors should either include the missing arguments in the present manuscript or provide a verifiable source (e.g., a published version of [2] or a machine-checked proof) for the claimed alternation behavior of A1 vertices in this exact construction.
[Algorithm 1, line 3] The loop 'for a ∈ I do' does not specify the order in which the vertices of I are processed. This matters because the algorithm replaces occurrences of labels in q1 and q2, and if two vertices share the same m_a, n_a, r_a, or l_a, the resulting word depends on the iteration order. No tie-breaking rule is given, and no order-independence claim is proved. The companion proof from [2] must cover such tie cases, but the present text does not state how they are resolved, so Algorithm 1 as written is not fully deterministic and the correctness of Lemmas 3-5 cannot be checked without additional information.
[Section 3, proof of Theorem 5] In the proof of transitivity, when both a and c belong to C, the paper rules out the resulting directed cycle by saying 'in view of Theorem 4, D is indeed a semi-transitive orientation and thus, D is acyclic.' As stated, Theorem 4 is an existence characterization of semi-transitive orientability via a labeling, not a statement about the particular orientation D defined in the proof. If acyclicity of D is needed for the argument, it should be verified directly for the three types A1, A2, A3, or the authors should cite a specific result that applies exactly to the constructed orientation D rather than to the existence of some semi-transitive orientation.

minor comments (4)

[Section 1, paragraph 1] In the sentence 'In [10], It was proved that...', the word 'It' should not be capitalized.
[Section 1, paragraph after Theorem 4] The notation [a, b] is defined only after Theorem 4 is stated, but Theorem 4 already uses brackets such as [1, m]; the definition should be given before the first use.
[Theorem 6, proof] The sentence 'If B4 is an induced subgraph of G, then clearly Rp(G) = 3' could be expanded to make the monotonicity argument explicit: Rp is monotone under induced subgraphs, and since Rp(B4) = 3 and Rp(G) ≤ 3, equality follows.
[General notation] The abbreviation prn is used before it is formally defined; the definition 'permutation-representation number (in short, prn)' appears only in a later parenthetical, so it would be clearer to introduce the abbreviation at first mention.

Circularity Check

2 steps flagged · score 4.0 of 10

Main upper-bound proof for Rp(G) ≤ 3 defers all A1-vertex alternation cases to the same authors' unpublished companion preprint [2]; this is load-bearing self-citation, though the A2/A3 parts and the B4 converse are independently derived.

self citation load bearing [Lemma 3, Case 1 (also Lemma 4, Case 1; Lemma 5, Case 1; justified by Remark 3), Section 4]
"Case 1: a∈ A1. In view of Remark 3 and Case 1 in the proof of Lemma 2 in [2], we conclude that a and b alternate in the word z. ... Remark 3. Note that, the set A⊆ I defined in Section 3 of [2] and the set A1 are identical for a split comparability graph G. Moreover, the lines related to insertion of the elements of A in p1, p2 and p3 in Algorithm 1 of [2] are exactly the same as the lines on insertion of the elements of A1 in q1, q2 and q3 in Algorithm 1."

The partition I = A1 ∪ A2 ∪ A3 from Theorem 5 shows A1 is an entire cell of the independent set, not a minor edge case. Lemmas 3, 4, and 5 each resolve the A1 case by saying 'in view of Remark 3 and Case 1... in [2]', and Remark 3 asserts that the set A in [2] is identical to A1 and that the insertion lines are 'exactly the same'. Thus the proof of the central inequality Rp(G) ≤ 3 for every pair involving an A1 vertex is not derived in this paper; it is transferred verbatim to an unpublished, non-machine-checked, same-author preprint [2]. The technical verification of one of the three independent-vertex classes therefore reduces to the authors' own prior claim rather than to an argument reproduced or independently established here.
self citation load bearing [Corollary 1 and Section 1 (dimension/prn equivalence)]
"It was reconciled in [13] that if G is a comparability graph, then Rp(G) is precisely the dimension of any induced partially ordered set (poset) of G. ... In view of the connection between the prn of a comparability graph and the dimension of its induced poset (cf. [13, Corollary 2]), Theorem 6 gives us an alternative proof for [5, Theorem 22], as stated in the following corollary."

The corollary's order-theoretic conclusion, that the dimension of an induced poset of a split comparability graph is at most three and tight, is obtained by combining Theorem 6 with [13, Corollary 2]. That bridge is a same-author arXiv result rather than a published, machine-checked, or externally reproduced theorem. The dependency is real but peripheral: it does not feed back into Theorem 6, and the main graph-theoretic claim stands or falls independently of [13], apart from the dimension interpretation.

full rationale

The paper is not circular in the definitional or fitted-input sense: Theorem 5 gives a concrete labelling characterization, Algorithm 1 explicitly constructs three permutations, and the A2/A3 cases in Lemmas 3-5 are argued directly in the paper without reusing the theorem being proved. The converse part of Theorem 6 (B4 characterization) is also self-contained, using cited published results [1,3,4]. The significant circularity-adjacent issue is that the A1 cases of all three alternation lemmas are justified entirely by Remark 3 plus the same authors' companion preprint [2], which is unpublished, contains the corresponding 'Case 1' proofs, and is not reproduced or machine-checked here. Since A1 is one of the three classes in the partition of the independent set, the main upper-bound proof is load-bearing on that self-citation for a whole class of vertices. A second, lower-stakes self-citation appears in the dimension corollary via [13]. These dependencies prevent a clean 0-2 score, but they do not amount to full circularity because the central construction has substantial independent content and the theorem is not equivalent to its own assumptions. Score 4.

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

No free parameters or invented entities. The derivation relies on four external results, two of which are same-author unpublished preprints ([2] and [13]); these carry the main circularity burden.

assumptions (5)

domain assumption The equivalence Rp(G)=dim(P) for any induced poset P of a comparability graph G, cited from [13, Corollary 2] (Mozhui and Krishna, arXiv:2311.13980), is correct.
Used in Corollary 1 to translate Rp(G)<=3 into dim(P)<=3. This is a same-author unpublished preprint at the time of submission.
ad hoc to paper The correctness of the construction and proof in [2, arXiv:2502.00872], specifically that vertices of A1 alternate and non-alternate as claimed, is assumed.
Remark 3 and Case 1 in the proofs of Lemmas 3, 4, and 5 defer entirely to [2] without reproducing the arguments.
domain assumption The forbidden induced subgraph characterizations of split permutation graphs (Theorem 1) and split comparability graphs (Theorem 2) from [1] and [4] are correct.
Used in Theorem 6 to identify B4 as the unique non-permutation split comparability graph.
domain assumption The semi-transitive orientation characterization of split graphs (Theorem 4 from [8,11]) is correct.
Used in the proof of Theorem 5 to derive properties (iii) to (v).
standard math The permutation-representation number of a graph is at least that of any induced subgraph.
Used implicitly in Theorem 6 to conclude Rp(G) >= 3 when B4 is an induced subgraph.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Characterization of Split Comparability Graphs." pith.science (2026). https://pith.science/paper/NM7SH3OJ

@misc{pith2026250419167,
  author       = {Pith},
  title        = {Pith review of: Characterization of Split Comparability Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NM7SH3OJ}},
  note         = {Machine review of arXiv:2504.19167}
}

read the original abstract

A split graph is a graph whose vertex set can be partitioned into a clique and an independent set. A split comparability graph is a split graph which is transitively orientable. In this work, we characterize split comparability graphs in terms of vertex labelling. Further, using this characterization, we prove that the permutation-representation number of a split comparability graph is at most three. This gives us an alternative proof of the result in order theory that the dimension of a split order is at most three.

Figures

Figures reproduced from arXiv: 2504.19167 by the authors.

**Figure 1.** The family of graphs B a permutation on the vertices of G; in this case G is called a permutationally k-representable graph. Moreover, we say w permutationally represents G. The permutation-representation number (in short, prn) of G, denoted by Rp (G), is the smallest number k such that G is permutationally k-representable. It was shown in [12] that a graph is permutationally representable if and only if it is a com… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 5 canonical work pages

[13]

Mozhui and K

K. Mozhui and K. V. Krishna. On the permutation-representation number of bipartite graphs using neighborhood graphs. arXiv:2311.13980, 2023

arXiv 2023
[2]

Dwary, K

T. Dwary, K. Mozhui, and K. V. Krishna. Representation number of word- representable split graphs. arXiv:2502.00872v2, 2025

arXiv 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 split graphs. Discrete Appl. Math. , 323:43–75, 2022

work page 2022
[3]

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

1967
[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. 10

work page 2004
[5]

Guenver and J.-X

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

2004
[6]

M. M. Halld´ orsson, S. Kitaev, and A. Pyatkin. Alternation 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-transitive orientations and word-representable graphs. Discrete Appl. Math. , 201:164–171, 2016

2016

Show all 14 references

[8]

Kitaev, Y

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

2021
[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 A

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

2024
[12]

Kitaev and S

S. Kitaev and S. Seif. Word problem of the Perkins semigroup via directed acyclic graphs. Order, 25(3):177–194, 2008

2008
[14]

Yannakakis

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

1982

Pith tools

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

[1] [13]

Mozhui and K

K. Mozhui and K. V. Krishna. On the permutation-representation number of bipartite graphs using neighborhood graphs. arXiv:2311.13980, 2023

arXiv 2023

[2] [2]

Dwary, K

T. Dwary, K. Mozhui, and K. V. Krishna. Representation number of word- representable split graphs. arXiv:2502.00872v2, 2025

arXiv 2025

[3] [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 split graphs. Discrete Appl. Math. , 323:43–75, 2022

work page 2022

[4] [3]

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

1967

[5] [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. 10

work page 2004

[6] [5]

Guenver and J.-X

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

2004

[7] [6]

M. M. Halld´ orsson, S. Kitaev, and A. Pyatkin. Alternation 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

[8] [7]

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

2016