Representation number of word-representable co-bipartite graph
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909768375861248 |
|---|---|
| author | Das, Biswajit Hariharasubramanian, Ramesh |
| author_facet | Das, Biswajit Hariharasubramanian, Ramesh |
| contents | A graph $G = (V, E)$ is said to be word-representable if there exists a word $w$ over the alphabet $V$ such that, for any two distinct letters $x, y \in V$, the letters $x$ and $y$ alternate in $w$ if and only if $xy \in E$. A graph is co-bipartite if its complement is bipartite. Therefore, the vertex set of a co-bipartite graph can be partitioned into two disjoint subsets $X$ and $Y$ such that the subgraphs induced by $X$ and $Y$ are cliques.
The concept of word-representability for graph classes has gained significant attention in recent years. The book Words and Graphs by Sergey Kitaev and Vadim Lozin presents examples of co-bipartite graphs that are not word-representable. It is known that a graph is word-representable if and only if it admits a semi-transitive orientation. Although the necessary and sufficient conditions for the existence of a semi-transitive orientation in co-bipartite graphs have been established, the characterization based on vertex ordering remains open. In this paper, we present necessary and sufficient conditions for a co-bipartite graph to be word-representable in terms of its vertex ordering. Furthermore, based on this vertex ordering, we provide an algorithm to construct a $3$-uniform word-representation for any word-representable co-bipartite graph. Using this result, we prove that except for the permutation graphs, the representation number of all other word-representable co-bipartite graphs is $3$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_03064 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Representation number of word-representable co-bipartite graph Das, Biswajit Hariharasubramanian, Ramesh Combinatorics Discrete Mathematics A graph $G = (V, E)$ is said to be word-representable if there exists a word $w$ over the alphabet $V$ such that, for any two distinct letters $x, y \in V$, the letters $x$ and $y$ alternate in $w$ if and only if $xy \in E$. A graph is co-bipartite if its complement is bipartite. Therefore, the vertex set of a co-bipartite graph can be partitioned into two disjoint subsets $X$ and $Y$ such that the subgraphs induced by $X$ and $Y$ are cliques. The concept of word-representability for graph classes has gained significant attention in recent years. The book Words and Graphs by Sergey Kitaev and Vadim Lozin presents examples of co-bipartite graphs that are not word-representable. It is known that a graph is word-representable if and only if it admits a semi-transitive orientation. Although the necessary and sufficient conditions for the existence of a semi-transitive orientation in co-bipartite graphs have been established, the characterization based on vertex ordering remains open. In this paper, we present necessary and sufficient conditions for a co-bipartite graph to be word-representable in terms of its vertex ordering. Furthermore, based on this vertex ordering, we provide an algorithm to construct a $3$-uniform word-representation for any word-representable co-bipartite graph. Using this result, we prove that except for the permutation graphs, the representation number of all other word-representable co-bipartite graphs is $3$. |
| title | Representation number of word-representable co-bipartite graph |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2509.03064 |