pith. sign in

arxiv: 2502.06979 · v3 · submitted 2025-02-10 · 💻 cs.DM

Word-representability and comparability: Minimal forbidden induced subgraphs and cover number bounds

Benny George Kenkireth , Gopalan Sajith , Sreyas Sasidharan This is my paper

Pith reviewed 2026-05-23 03:37 UTC · model grok-4.3

classification 💻 cs.DM
keywords word-representable graphscomparability graphscover numberminimal forbidden induced subgraphscircle graphssemi-transitive orientations
0
0 comments X

The pith

Word-representable graphs on n vertices exist whose cover number by comparability graphs is Omega(log n).

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

The paper classifies every minimal non-comparability graph to decide whether it is also minimal non-word-representable, then gives a complete list of the minimal non-word-representable graphs that contain a vertex adjacent to all others. It constructs explicit word-representable graphs on n vertices whose edges cannot be covered by fewer than Omega(log n) comparability graphs, proving the known O(log n) upper bound is tight even inside the word-representable class. The paper further shows that triangle-free circle graphs need at most three comparability graphs for a cover and that this number is sometimes achieved, while circle graphs whose largest clique is at least 24 need at most two.

Core claim

There exist word-representable graphs whose cover number by comparability graphs is Omega(log n), so the universal O(log n) upper bound is asymptotically tight for the class. The paper also determines precisely which minimal non-comparability graphs are word-representable and supplies a full description of the minimal non-word-representable graphs that contain an all-adjacent vertex.

What carries the argument

The cover number of a graph by comparability graphs (the minimum number of comparability graphs whose union equals the edge set of the given graph); the explicit constructions of word-representable graphs that force this number to be Omega(log n).

If this is right

  • The O(log n) upper bound on cover number is tight for word-representable graphs.
  • Triangle-free circle graphs have cover number at most 3 and the bound is tight.
  • Any circle graph with clique number at least 24 has cover number at most 2.
  • Every graph in each of four named subclasses of word-representable graphs has cover number at most 2.

Where Pith is reading between the lines

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

  • The same logarithmic lower bound may hold inside other hereditary classes that properly contain the comparability graphs.
  • The classification of minimal forbidden subgraphs could be used to decide word-representability for the special case of graphs that contain a universal vertex.
  • The constructions might be modified to produce word-representable graphs whose cover number is larger than any constant multiple of log n.

Load-bearing premise

The graphs built to achieve the Omega(log n) lower bound must admit semi-transitive orientations.

What would settle it

An explicit cover of one of the constructed graphs by o(log n) comparability graphs, or a proof that one of those graphs has no semi-transitive orientation.

Figures

Figures reproduced from arXiv: 2502.06979 by Benny George Kenkireth, Gopalan Sajith, Sreyas Sasidharan.

Figure 1
Figure 1. Figure 1: G1 is a word-representable graph and G2 is a non-word-representable graph. Example 2. The graph G1 in Figure 1a is an example of a word-representable graph. The word w = 6123564 represents G1. The graph G2 in Figure 1b is the Wheel graph W5 on six vertices. Definition 3. A class of graphs X is said to be hereditary if, for any graph G ∈ X, all induced subgraphs of G belong to the class X. Example 3. Planar… view at source ↗
Figure 2
Figure 2. Figure 2: G1 is minimal non-word-representable graph, where as G2 is non-minimal non-word-representable graph. Example 5. The graph G1 in Figure 2a is an example of a minimal non-word￾representable graph. G1 is the Wheel graph W5 on six vertices. The graph G2 in Figure 2b contains Wheel graph W5 as an induced subgraph, and hence G2 is a non-minimal non-word-representable graph. The notion of semi-transitivity is ver… view at source ↗
Figure 3
Figure 3. Figure 3: A semi-transitive orientation. Theorem 1 is significant as it establishes that a graph is word-representable if and only if it is semi-transitive. This result suggests that to prove a graph G is word-representable, it is sufficient to demonstrate that G is semi-transitive. Theorem 1. [5] A graph G is word-representable if and only if it admits a semi-transitive orientation. Definition 8. Let G be a directe… view at source ↗
Figure 4
Figure 4. Figure 4: G1 is a comparability graph and G2 is a non-comparability graph. Example 8. Figure 4a shows an example of a comparability graph, and Figure 4b provides one of its transitive orientations. G2 in Figure 4c is C5, which is known to be a non-comparability graph [2]. Comparability graphs form a subclass of word-representable graphs [5]. The class of comparability graphs is hereditary, and hence, a forbidden ind… view at source ↗
Figure 5
Figure 5. Figure 5: G1 is a minimal non-comparability graph and G2 is non-minimal non￾comparability graph. Gallai provided the forbidden induced subgraph characterization for compa￾rability graphs in [2]. Gallai identified the complete list of minimal forbidden induced subgraphs for comparability graphs, which are precisely what we call minimal non-comparability graphs. The list of all minimal non-comparability graphs is give… view at source ↗
Figure 6
Figure 6. Figure 6: Minimal non-comparability graphs - 1 (Four infinite classes of graphs.) a1 b1 a2 b2 .... an bn (a) G 5 n ; n ≥ 3 a1 b1 a2 b2 .... an bn c0 (b) G 6 n ; n ≥ 3 [PITH_FULL_IMAGE:figures/full_fig_p008_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Minimal non-comparability graphs - 2 (Two infinite classes of graphs, where only the missing edges are highlighted. Dashed edges represent absent connections, while all other edges are present.) [PITH_FULL_IMAGE:figures/full_fig_p008_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Minimal non-comparability graphs - 3 (Three infinite graph classes, each structured into three levels. Due to the complexity of these graphs, dashed edges are used in certain levels to indicate the only missing edges within that level.) [PITH_FULL_IMAGE:figures/full_fig_p009_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Minimal non-comparability graphs - 4 [PITH_FULL_IMAGE:figures/full_fig_p010_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: 3-colorable minimal non-comparability graph classes From Theorem 4 and Theorem 3, we have the following Corollary 1. Corollary 1. The class of graphs G1 n, G2 n, and G3 n form a subclass of word￾representable graphs. Theorem 5. The class of graphs G5 n depicted in Figure 7a form a subclass of word-representable graphs. Proof. Consider an arbitrary graph G ∈ G5 n , where |V (G)| = 2n and |E(G)| = 2n 2  − … view at source ↗
Figure 11
Figure 11. Figure 11: A semi-transitive orientation of edges of [PITH_FULL_IMAGE:figures/full_fig_p012_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: This orientation is acyclic. For the sake of contr [PITH_FULL_IMAGE:figures/full_fig_p013_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: A semi-transitive orientation of edges of [PITH_FULL_IMAGE:figures/full_fig_p014_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: A semi-transitive orientation of edges of [PITH_FULL_IMAGE:figures/full_fig_p015_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Semi-transitive orientations of graphs in Figure 9 [PITH_FULL_IMAGE:figures/full_fig_p016_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: Four semi-transitive orientations of G′′ U , with 1 as a source [PITH_FULL_IMAGE:figures/full_fig_p020_16.png] view at source ↗
read the original abstract

Word-representable graphs, characterized by the existence of a semi-transitive orientation, form a well-studied class of graphs. Comparability graphs form another well-studied class and constitute a subclass of word-representable graphs. Both classes are hereditary and admit characterizations in terms of minimal forbidden induced subgraphs. While the minimal forbidden induced subgraphs for comparability graphs are completely characterized, the corresponding characterization for word-representable graphs remains open. In this paper, we precisely determine which minimal non-comparability graphs are also minimal non-word-representable graphs by classifying minimal non-comparability graphs according to whether they are word-representable. As a consequence, we provide a complete description of minimal non-word-representable graphs containing an all-adjacent vertex. We also address an open problem posed by Kenkireth et al.\ concerning the cover number of word-representable graphs by comparability graphs. We demonstrate the existence of word-representable graphs on $n$ vertices whose cover number by comparability graphs is $\Omega(\log n)$, which establishes that the universal $O(\log n)$ upper bound is asymptotically tight for the class of word-representable graphs. For triangle-free circle graphs, we establish that the cover number by comparability graphs is at most $3$ and demonstrate that this bound is tight. More generally, we prove that for any circle graph $G$ with clique number $\omega(G) \ge 24$, the cover number by comparability graphs is at most $2$. Finally, we identify four subclasses of word-representable graphs for which the cover number by comparability graphs of every graph in these classes is at most $2$.

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.

Referee Report

1 major / 2 minor

Summary. The paper classifies which minimal non-comparability graphs are minimal non-word-representable, gives a complete description of minimal non-word-representable graphs containing a universal vertex, constructs word-representable graphs on n vertices with comparability cover number Ω(log n) to show the known O(log n) upper bound is tight, proves that triangle-free circle graphs have cover number at most 3 (and that this is tight), shows that circle graphs with ω(G) ≥ 24 have cover number at most 2, and identifies four subclasses of word-representable graphs with cover number at most 2.

Significance. The classification of minimal non-comparability graphs advances the open problem of characterizing minimal forbidden induced subgraphs for word-representable graphs and supplies an explicit description for the universal-vertex case. The Ω(log n) lower-bound constructions, if the word-representability verification is complete, establish asymptotic tightness for the cover-number problem posed by Kenkireth et al. The concrete upper bounds for circle graphs and the four subclasses are useful refinements within the hereditary class.

major comments (1)
  1. [section on cover-number lower bounds] The constructions establishing the Ω(log n) lower bound on comparability cover number (the section addressing the open problem of Kenkireth et al.) must supply, for each family G_n, either an explicit semi-transitive orientation or a proof that none of the known minimal non-word-representable graphs appear as induced subgraphs. The abstract states that the graphs are word-representable, but any gap in this verification step leaves the tightness claim unsupported even if the cover-number calculation itself is correct.
minor comments (2)
  1. The abstract refers to 'the universal O(log n) upper bound' without a forward reference to the theorem or paper that established it; adding the citation would improve readability.
  2. Notation for the cover number (e.g., whether it is denoted c(G) or another symbol) should be introduced consistently in the first paragraph of the relevant section.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address the single major comment below.

read point-by-point responses

  1. Referee: [section on cover-number lower bounds] The constructions establishing the Ω(log n) lower bound on comparability cover number (the section addressing the open problem of Kenkireth et al.) must supply, for each family G_n, either an explicit semi-transitive orientation or a proof that none of the known minimal non-word-representable graphs appear as induced subgraphs. The abstract states that the graphs are word-representable, but any gap in this verification step leaves the tightness claim unsupported even if the cover-number calculation itself is correct.

    Authors: We agree that the word-representability of each constructed family G_n must be verified explicitly to support the tightness claim. In the revised manuscript we will supply, for every such family, either an explicit semi-transitive orientation or a proof that none of the known minimal non-word-representable graphs appear as induced subgraphs. revision: yes

Circularity Check

0 steps flagged

No circularity: independent constructions and case analysis

full rationale

The paper's central results—classification of minimal non-comparability graphs that are word-representable, explicit Ω(log n) constructions for cover number, and bounds for circle graphs—rely on direct forbidden-subgraph case analysis and explicit graph families. These steps are self-contained against external graph-theoretic definitions (semi-transitive orientations, comparability covers) without reducing any claimed prediction or bound to a fitted parameter, self-citation chain, or definitional tautology. No equations equate outputs to inputs by construction, and the lower-bound families are asserted to be word-representable via the paper's own induced-subgraph checks rather than prior self-citations. This is the normal non-circular outcome for a combinatorial classification paper.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard domain assumptions from graph theory; no free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (2)
  • domain assumption Word-representable graphs are exactly the graphs admitting a semi-transitive orientation.
    Invoked as the working characterization throughout the abstract.
  • domain assumption Comparability graphs form a proper subclass of word-representable graphs.
    Stated explicitly as background for the classification task.

pith-pipeline@v0.9.0 · 5853 in / 1355 out tokens · 58658 ms · 2026-05-23T03:37:08.294882+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages · 1 internal anchor

  1. [2]

    Acta Mathematica Academiae Scientiarum Hungarica 18, 25--66 (1967), https://api.semanticscholar.org/CorpusID:119485995

    Gallai, T.: Transitiv orientierbare graphen. Acta Mathematica Academiae Scientiarum Hungarica 18, 25--66 (1967), https://api.semanticscholar.org/CorpusID:119485995

    work page 1967

  2. [3]

    In: Kolman, P., Kratochv \'i l, J

    Halld \'o rsson, M.M., Kitaev, S., Pyatkin, A.: Alternation graphs. In: Kolman, P., Kratochv \'i l, J. (eds.) Graph-Theoretic Concepts in Computer Science. pp. 191--202. Springer Berlin Heidelberg, Berlin, Heidelberg (2011)

    work page 2011

  3. [4]

    Kitaev, S.: A comprehensive introduction to the theory of word-representable graphs. vol. 10396, pp. 36--67 (07 2017). doi:10.1007/978-3-319-62809-7_2

    work page doi:10.1007/978-3-319-62809-7_2 2017

  4. [5]

    Springer, Cham (2015)

    Kitaev, S., Lozin, V.: Words and Graphs. Springer, Cham (2015). doi:https://doi.org/10.1007/978-3-319-25859-1

    work page doi:10.1007/978-3-319-25859-1 2015

  5. [6]

    Journal of Automata, Languages and Combinatorics 13, 45--54 (01 2008)

    Kitaev, S., Pyatkin, A.: On representable graphs. Journal of Automata, Languages and Combinatorics 13, 45--54 (01 2008)

    work page 2008

  6. [9]

    Discrete Math

    Ahn, J., Jaffke, L., Kwon, O., Lima, P.T.: Well-partitioned chordal graphs. Discrete Math. 345(10), 112985 (2022). doi:10.1016/j.disc.2022.112985

    work page doi:10.1016/j.disc.2022.112985 2022

  7. [10]

    In: George, A., Gilbert, J.R., Liu, J.W.H

    Blair, J.R.S., Peyton, B.: An Introduction to Chordal Graphs and Clique Trees. In: George, A., Gilbert, J.R., Liu, J.W.H. (eds.) Graph Theory and Sparse Matrix Computation, pp. 1--29. Springer, New York (1993)

    work page 1993

  8. [11]

    Bender, E., Richmond, L., Wormald, N.: Almost all chordal graphs split. J. Aust. Math. Soc. 38, 214--221 (1985). doi:10.1017/S1446788700023077

    work page doi:10.1017/s1446788700023077 1985

  9. [12]

    Discrete Appl

    Collins, A., Kitaev, S., Lozin, V.: New results on word-representable graphs. Discrete Appl. Math. 216, 201--209 (2014). doi:10.1016/j.dam.2014.10.024

    work page doi:10.1016/j.dam.2014.10.024 2014

  10. [13]

    Discrete Math

    Cornuéjols, G., Liu, Y., Vušković, K.: Recognition of even-hole-free graphs. Discrete Math. 224(1--3), 55--61 (2000)

    work page 2000

  11. [14]

    Farber, M., Jamison, R.E.: Applications of perfect graphs to communication complexity. J. Comb. Theory Ser. B 43(1), 50--63 (1987)

    work page 1987

  12. [15]

    Acta Math

    Gallai, T.: Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hung. 18, 25--66 (1967)

    work page 1967

  13. [16]

    In: Algorithmic Graph Theory and Perfect Graphs, Ann

    Golumbic, M.C.: Chapter 4 - Triangulated graphs. In: Algorithmic Graph Theory and Perfect Graphs, Ann. Discrete Math., vol. 57, pp. 81--104. Elsevier (2004). doi:10.1016/S0167-5060(04)80052-9

    work page doi:10.1016/s0167-5060(04)80052-9 2004

  14. [17]

    Combinatorica 1(2), 169--197 (1981)

    Grötschel, M., Lovász, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169--197 (1981)

    work page 1981

  15. [18]

    Discrete Math

    Hougardy, S.: Classes of perfect graphs. Discrete Math. 306(19), 2529--2571 (2006). doi:10.1016/j.disc.2006.05.021

    work page doi:10.1016/j.disc.2006.05.021 2006

  16. [19]

    In: Drewes, F., Volkov, M

    Kenkireth, B.G., Malhotra, A.S.: On Word-Representable and Multi-word-Representable Graphs. In: Drewes, F., Volkov, M. (eds.) Developments in Language Theory, pp. 156--167. Springer, Cham (2023)

    work page 2023

  17. [20]

    Kitaev, S., Pyatkin, A.: On Representable Graphs. J. Autom. Lang. Comb. 13, 45--54 (2008)

    work page 2008

  18. [21]

    In: Charlier, É., Leroy, J., Rigo, M

    Kitaev, S.: A Comprehensive Introduction to the Theory of Word-Representable Graphs. In: Charlier, É., Leroy, J., Rigo, M. (eds.) Developments in Language Theory. LNCS, vol. 10396, pp. 36--67. Springer, Cham (2017). doi:10.1007/978-3-319-62809-7\_2

    work page doi:10.1007/978-3-319-62809-7 2017

  19. [22]

    RAIRO - Theor

    Kitaev, S., Sun, H.: Human-verifiable proofs in the theory of word-representable graphs. RAIRO - Theor. Inf. Appl. 58, 9 (2024). doi:10.1051/ita/2024004

    work page doi:10.1051/ita/2024004 2024

  20. [23]

    Order 25, 177--194 (2008)

    Kitaev, S., Seif, S.: Word Problem of the Perkins Semigroup via Directed Acyclic Graphs. Order 25, 177--194 (2008). doi:10.1007/s11083-008-9083-7

    work page doi:10.1007/s11083-008-9083-7 2008

  21. [24]

    Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs

    Konrad, C., Zamaraev, V.: Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs. arXiv preprint (2018). https://arxiv.org/abs/1805.04544

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  22. [25]

    IEEE Trans

    Lovász, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 23(1), 1--7 (1972)

    work page 1972

  23. [26]

    SIAM, Philadelphia (1999)

    McKee, T.A., McMorris, F.R.: Topics in Intersection Graph Theory. SIAM, Philadelphia (1999)

    work page 1999

  24. [27]

    Perkins, T.: A Comprehensive Guide to Graphs. J. Math. Sci. 23(5), 689--704 (2008)

    work page 2008

  25. [28]

    GitHub repository (2024)

    Sasidharan, S.: Word-representable-Induced-subgraph-check-programs. GitHub repository (2024). Available at: https://github.com/sreyas-s/Word-representable-Induced-subgraph-check-programs

    work page 2024

  26. [29]

    SIAM Rev

    Tucker, A.: Perfect Graphs and an Application to Optimizing Municipal Services. SIAM Rev. 15(3), 585--590 (1973)

    work page 1973

  27. [30]

    Wagner, R., Laufer, D., Sierke, G.: Graph-theoretic modeling of large-scale semantic networks in biology. J. Chem. Inf. Model. 48(2), 286--297 (2008)

    work page 2008

  28. [31]

    Journal 2(5), 99--110 (2016)

    Author, F.: Article title. Journal 2(5), 99--110 (2016)

    work page 2016

  29. [32]

    In: Editor, F., Editor, S

    Author, F., Author, S.: Title of a proceedings paper. In: Editor, F., Editor, S. (eds.) CONFERENCE 2016, LNCS, vol. 9999, pp. 1--13. Springer, Heidelberg (2016). doi:10.10007/1234567890

    work page doi:10.10007/1234567890 2016

  30. [33]

    Author, F., Author, S., Author, T.: Book title. 2nd edn. Publisher, Location (1999)

    work page 1999

  31. [34]

    In: 9th International Proceedings on Proceedings, pp

    Author, A.-B.: Contribution title. In: 9th International Proceedings on Proceedings, pp. 1--2. Publisher, Location (2010)

    work page 2010

  32. [35]

    LNCS Homepage, http://www.springer.com/lncs, last accessed 2023/10/25

    work page 2023

  33. [36]

    , " * write output.state after.block = add.period write

    ENTRY address author booktitle chapter doi edition editor eid howpublished institution journal key month note number organization pages publisher school series title type url volume year label INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.all := #1 'mid.sentence := #2 'after.sentence := #3 '...

    work page

  34. [37]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize ":" * " " *...

    work page