pith. sign in

arxiv: 2512.12274 · v2 · submitted 2025-12-13 · 🧮 math.CO · cs.DM

Forbidden Induced Subgraph Characterization of Word-Representable Co-bipartite Graphs

Eshwar Srinivasan , Ramesh Hariharasubramanian This is my paper

Pith reviewed 2026-05-16 22:59 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords word-representable graphsco-bipartite graphscircle graphspermutation graphssemi-transitive orientationsforbidden induced subgraphslinear-time recognition
0
0 comments X

The pith

A co-bipartite graph is word-representable if and only if it is a circle graph if and only if it is a permutation graph.

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

The paper establishes that for graphs whose vertices can be partitioned into two cliques, word-representability is equivalent to being a circle graph and to being a permutation graph. This equivalence is shown by proving that such graphs are word-representable precisely when their adjacency matrices have the circularly compatible ones property. The characterization also yields a minimal forbidden induced subgraph set and a linear-time recognition algorithm based on matrix methods. Sympathetic readers care because it simplifies checking a complex property in a natural subclass and unifies several well-known graph families.

Core claim

Co-bipartite graphs are word-representable if and only if they are circle graphs if and only if they are permutation graphs, and this occurs exactly when their adjacency matrices possess the circularly compatible ones property, providing both a structural forbidden-subgraph description and an efficient recognition procedure.

What carries the argument

The circularly compatible ones property of the adjacency matrix, which the paper shows is equivalent to the existence of a semi-transitive orientation in the co-bipartite case.

Load-bearing premise

The known equivalence between word-representability and semi-transitive orientations extends to co-bipartite graphs, and the circularly compatible ones property exactly captures semi-transitivity for their adjacency matrices.

What would settle it

A co-bipartite graph that admits a semi-transitive orientation but whose adjacency matrix lacks the circularly compatible ones property, or a co-bipartite circle graph that is not word-representable.

Figures

Figures reproduced from arXiv: 2512.12274 by Eshwar Srinivasan, Ramesh Hariharasubramanian.

Figure 1
Figure 1. Figure 1: Minimal forbidden induced subgraphs for co-bipartite permutation graphs, [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Circle graph obstructions. Therefore, for the above three cases, by Theorem 6, it follows that G is not a circle graph. Hence, suppose that G ∼= C2k for some k ≥ 3. Assume, for the sake of contradiction, that G is a circle graph. This implies that there exists a 2-uniform word-representant of G, say wG. Consider the graph H ∼= G[NG[1]]. By Theorem 5 and the hereditary nature of circle graphs, it can be see… view at source ↗
Figure 3
Figure 3. Figure 3: Some matrices in F∞ CCO The following result from [29], which will be used in the proof of the main theorem of this section, provides a minimal forbidden submatrix characterization of matrices possessing the circularly compatible ones property. Theorem 12 ([29]). For any matrix M, the following statements are equivalent: 11 [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Shortcut possibilities 12 [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Minimal forbidden induced subgraphs for semi-transitive co-bipartite graphs, [PITH_FULL_IMAGE:figures/full_fig_p016_5.png] view at source ↗
read the original abstract

A graph $G$ with vertex set $V(G)$ and edge set $E(G)$ is said to be word-representable if there exists a word $w$ over the alphabet $V(G)$ such that, for any two distinct letters $x,y \in V(G)$, the letters $x$ and $y$ alternate in $w$ if and only if $(x,y) \in E(G)$. Equivalently, a graph is word-representable if and only if it admits a semi-transitive orientation, that is, an acyclic orientation in which, for every directed path $v_0 \rightarrow v_1 \rightarrow \cdots \rightarrow v_m$ with $m \ge 2$, either there is no arc between $v_0$ and $v_m$, or, for all $1 \le i < j \le m$, there exists an arc from $v_i$ to $v_j$. In this work, we provide a comprehensive structural and algorithmic characterization of word-representable co-bipartite graphs, a class of graphs whose vertex set can be partitioned into two cliques. This work unifies graph-theoretic and matrix-theoretic perspectives. We first establish that a co-bipartite graph is a circle graph if and only if it is a permutation graph, thereby deriving a minimal forbidden induced subgraph characterization for co-bipartite circle graphs. The central contribution then connects semi-transitivity with the circularly compatible ones property of binary matrices. In addition to the structural characterization, the paper introduces a linear-time recognition algorithm for semi-transitive co-bipartite graphs, utilizing Safe's matrix recognition framework.

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 / 3 minor

Summary. The manuscript claims that a co-bipartite graph is word-representable if and only if it is a circle graph if and only if it is a permutation graph. It derives a minimal forbidden induced subgraph characterization for this class and shows equivalence to the adjacency matrix (block-structured with two all-ones diagonal blocks and a biadjacency block) satisfying the circularly compatible ones property. This yields a linear-time recognition algorithm by direct application of Safe's matrix recognition framework to semi-transitive orientations.

Significance. If the equivalences hold, the paper supplies a complete structural characterization via forbidden subgraphs together with an efficient recognition procedure for word-representable graphs inside the co-bipartite family. The explicit linkage between semi-transitive orientations and the matrix property, combined with the use of an established recognition framework, constitutes a concrete algorithmic contribution and unifies combinatorial and matrix-theoretic viewpoints on this subclass.

major comments (1)
  1. [§4, Theorem 4.1] §4, Theorem 4.1: the bidirectional equivalence between semi-transitivity and the circularly compatible ones property on the block adjacency matrix is asserted by specializing the general word-representable characterization, but the argument does not explicitly verify that the all-ones blocks impose no extra constraints on the orientation conditions; a short case analysis for paths that cross the bipartition would make the reduction load-bearing.
minor comments (3)
  1. [Abstract] Abstract: the statement of the linear-time algorithm would benefit from naming the precise time bound (O(n+m)) and citing Safe's framework in the same sentence.
  2. [§3.2] §3.2: the notation for the biadjacency block B in the adjacency matrix is introduced without an accompanying small example matrix; adding one would clarify how the circularly compatible ones condition is checked on B.
  3. [Figure 3] Figure 3: the drawing of the minimal forbidden co-bipartite subgraph lacks vertex labels corresponding to the clique partition; this reduces readability when comparing to the matrix condition.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive suggestion. We agree that the argument in Theorem 4.1 would benefit from an explicit verification that the all-ones blocks introduce no additional constraints, and we will incorporate a short case analysis in the revision.

read point-by-point responses

  1. Referee: [§4, Theorem 4.1] §4, Theorem 4.1: the bidirectional equivalence between semi-transitivity and the circularly compatible ones property on the block adjacency matrix is asserted by specializing the general word-representable characterization, but the argument does not explicitly verify that the all-ones blocks impose no extra constraints on the orientation conditions; a short case analysis for paths that cross the bipartition would make the reduction load-bearing.

    Authors: We agree that the current presentation would be strengthened by an explicit check. In the revised manuscript we will add a short case analysis immediately after the statement of Theorem 4.1. For any directed path that crosses the bipartition, the two all-ones diagonal blocks ensure that the endpoints are adjacent whenever the path length is at least 2; consequently the semi-transitivity condition reduces exactly to the circularly compatible ones property on the off-diagonal block, with no further restrictions. This makes the specialization of the general word-representable characterization fully rigorous while preserving the linear-time recognition via Safe’s framework. revision: yes

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper establishes the equivalence of word-representable co-bipartite graphs with co-bipartite circle graphs (equivalently permutation graphs) via a structural proof that yields a forbidden induced subgraph characterization. It then links semi-transitivity to the circularly compatible ones property on the block-structured adjacency matrices (two all-ones blocks plus biadjacency) and applies Safe's external matrix recognition framework to obtain the linear-time algorithm. No load-bearing step reduces a central claim to a self-definition, a fitted parameter renamed as prediction, or a self-citation chain; the equivalences rest on independently verifiable graph-theoretic arguments and an external algorithmic tool rather than internal construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on two prior equivalences and standard definitions of co-bipartite graphs and matrix properties; no numerical parameters or new postulated objects are introduced.

axioms (2)
  • domain assumption A graph is word-representable if and only if it admits a semi-transitive orientation.
    Invoked in the abstract as the starting equivalence for the entire development.
  • domain assumption Co-bipartite graphs admit a natural bipartition into two cliques whose adjacency matrix encodes the orientation constraints.
    Used to reduce the problem to matrix recognition.

pith-pipeline@v0.9.0 · 5609 in / 1321 out tokens · 45347 ms · 2026-05-16T22:59:07.370927+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

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

  1. On Languages Describing Large Graph Classes

    cs.FL 2026-04 unverdicted novelty 6.0

    Formal binary languages can represent graph classes by using their words as patterns to define edges, with languages such as palindromes and Dyck words able to describe all graphs or particular graph classes via suita...

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages · cited by 1 Pith paper

  1. [1]

    A. Basu, S. Das, S. Ghosh, and M. Sen. Circular-arc bigraphs and its subclasses.J. Graph Theory, 73(4):361–376, 2013

    work page 2013

  2. [2]

    A. Bouchet. Circle graph obstructions.J. Combin. Theory Ser. B, 60(1):107–144, 1994

    work page 1994

  3. [3]

    B. Broere. Word-representable graphs, 2018. Master’s thesis, Radboud Univ. Nijmegen

    work page 2018

  4. [4]

    H. Z. Q. Chen, H. Hameed, and S. Kitaev. On the word-representability ofk m −k n graphs.Discuss. Math. Graph Theory, 2025

    work page 2025

  5. [5]

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

    work page 2022

  6. [6]

    D. G. Corneil, H. Lerchs, and L. S. Burlingham. Complement reducible graphs.Discrete Appl. Math., 3:163–174, 1981

    work page 1981

  7. [7]

    Das and H

    B. Das and H. Ramesh. Representation number of word-representable co-bipartite graphs.arXiv Preprint, 2025

    work page 2025

  8. [8]

    Das and H

    B. Das and H. Ramesh. Word-representability of co-bipartite graphs.arXiv Preprint, 2025

    work page 2025

  9. [9]

    Eshwar and H

    S. Eshwar and H. Ramesh. Minimum length word-representants of word-representable graphs.Dis- crete Appl. Math., 343:149–158, 2024

    work page 2024

  10. [10]

    Esperet and M

    L. Esperet and M. Stehlík. Bipartite complements of circle graphs.Discrete Math., 343(6):111834, 2, 2020

    work page 2020

  11. [11]

    Fleischmann, L

    P. Fleischmann, L. Haschke, T. Löck, and D. Nowotka. Word-representable graphs from a word’s perspective. InInternational Conference on Current Trends in Theory and Practice of Computer Science, pages 255–268. Springer, 2024

    work page 2024

  12. [12]

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

    work page 1967

  13. [13]

    M. C. Golumbic.Algorithmic Graph Theory and Perfect Graphs. Academic Press, 1980

    work page 1980

  14. [14]

    M. M. Halldórsson, S. Kitaev, and A. Pyatkin. Alternation graphs. InProc. 37th Int. Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 6986 ofLNCS, pages 191–202. Springer, 2011

    work page 2011

  15. [15]

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

    work page 2016

  16. [16]

    Huang, S

    S. Huang, S. Kitaev, and A. Pyatkin. An embedding technique in the study of word-representability of graphs.Discrete Appl. Math., 346:170–182, 2024. 17

    work page 2024

  17. [17]

    Iamthong

    K. Iamthong. Word-representability of split graphs generated by morphisms.Discrete Appl. Math., 314:284–303, 2022

    work page 2022

  18. [18]

    Iamthong and S

    K. Iamthong and S. Kitaev. Semi-transitivity of directed split graphs generated by morphisms.J. Combin., 14(1), 2023

    work page 2023

  19. [19]

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

    work page 2013

  20. [20]

    S. Kitaev. A comprehensive introduction to the theory of word-representable graphs. InDevelopments in Language Theory: 21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings, pages 36–67. Springer, 2017

    work page 2017

  21. [21]

    Kitaev, Y

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

    work page 2021

  22. [22]

    Kitaev and V

    S. Kitaev and V . Lozin.Words and Graphs. Springer, 2015

    work page 2015

  23. [23]

    Kitaev and A

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

    work page 2008

  24. [24]

    Kitaev and A

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

    work page 2024

  25. [25]

    Kitaev, P

    S. Kitaev, P. Salimov, C. Severs, and H. Úlfarsson. On the representability of line graphs. InDevelop- ments in Language Theory: 15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011. Proceedings 15, pages 478–479. Springer, 2011

    work page 2011

  26. [26]

    Kitaev and S

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

    work page 2008

  27. [27]

    Kitaev and H

    S. Kitaev and H. Sun. Human-verifiable proofs in the theory of word-representable graphs.RAIRO Theor. Inform. Appl., 58:9, 2024

    work page 2024

  28. [28]

    M. D. Safe. Characterization and linear-time detection of minimal obstructions to concave-round graphs and the circular-ones property.J. Graph Theory, 93:268–298, 2020

    work page 2020

  29. [29]

    M. D. Safe. Circularly compatible ones, d-circularity, and proper circular-arc bigraphs.SIAM J. Discrete Math., 35(2):707–751, 2021

    work page 2021

  30. [30]

    J. Sawada. Generating bracelets in constant amortized time.SIAM J. Comput., 31(1):259–268, 2001

    work page 2001

  31. [31]

    Suchanda and H

    R. Suchanda and H. Ramesh. Word-representability of split graphs with independent set of size 4. arXiv preprint arXiv:2507.08483, 2025

    work page arXiv 2025

  32. [32]

    A. C. Tucker.Two Characterizations of Proper Circular-arc Graphs. ProQuest LLC, Ann Arbor, MI,

    work page

  33. [33]

    Thesis (Ph.D.)–Stanford University

    work page

  34. [34]

    A. C. Tucker. Matrix characterizations of circular-arc graphs.Pacific J. Math., 39:535–545, 1971

    work page 1971

  35. [35]

    D. B. West.Introduction to Graph Theory. Prentice Hall, 1996. 18

    work page 1996