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

arXiv:2502.06979 · cs.DM · Submitted 2025-02-10 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Word-representability and comparability".

Jane: Here's the gist of the paper. Word-representable graphs and comparability graphs are hereditary graph classes characterized by forbidden induced subgraphs, and this paper precisely determines which minimal non-comparability graphs are also minimal non-word-representable, while also addressing the cover number of word-representable graphs by comparability graphs <ref:2502.06979#pg2> The authors provide a complete description of minimal non-wordrepresentable graphs containing an all-adjacent vertex and establish asymptotic tightness for the universal O(log n) upper bound on the cover number by comparability graphs for word-representable graphs <ref:2502.06979#pg14>.

Tom: Classification of Minimal Forbidden Structures The paper resolves Problem 1 by classifying minimal non-comparability graphs into word-representable and non-word-representable cases, explicitly identifying the intersection between the classes of minimal non-comparability and minimal nonword-representable graphs <ref:2502.06979#pg12>.

Jane: Specifically, Theorem 5 identifies the word-representable minimal non-comparability graphs as all graphs in families G1n, G2n, G3n, G5n, G6n, G7n, and G8n together with H2 through H11 and G92 <ref:2502.06979#pg11>.

Tom: Conversely, Theorem 6 identifies the non-word-representable minimal non-comparability graphs as all graphs in families G4n and G9n for n ≥ 3, along with graph H1 <ref:2502.06979#pg13>.

Title and authors: Tom: Let's start by looking at the title and the authors of "Word-representability and comparability: Minimal forbidden induced subgraphs and cover number bounds." The authors are Benny George Kenkireth, Gopalan Sajith, and Sreyas Sasidharan.

Jane: It sounds like they are doing a deep dive into how word-representable graphs relate to comparability graphs, which is a key relationship since comparability graphs are a subclass of word-representable graphs.

Lu: The paper focuses on the minimal forbidden induced subgraphs for these classes, and it resolves the open problem of identifying which minimal non-comparability graphs are also minimal non-word-representable by classifying them into word-representable or non-word-representable cases.

Meng: So, they are using that classification to give a complete description of these specific graph structures that cause trouble for word representability when compared to comparability.

Lalam: Specifically, they identify the intersection between minimal non-comparability and minimal non-word-representable graphs, which is a big step in characterizing the forbidden structures.

The paper's summary: Tom: Moving on to the summary of "Word-representability and comparability: Minimal forbidden induced subgraphs and cover number bounds," they are summarizing their findings on both problems.

Jane: They're summarizing that Problem one is solved by classifying minimal non-comparability graphs, and Problem two involves determining the cover number of a word-representable graph by comparability graphs <ref:2502.06979#pg2>.

Lu: For Problem two they show that the universal upper bound of O log n for the cover number by comparability graphs for word-representable graphs is actually asymptotically tight, meaning there are words with n vertices whose cover number is on the order of log n <ref:2502.06979#pg2,cover number by comparability graphs>.

Meng: That tightness result is important because it tells us that we can't just rely on a simple upper bound; there are examples where that bound is reached in the worst case.

Lalam: And they also give specific bounds for subclasses, like triangle-free circle graphs, showing their cover number by comparability graphs is at most three and that this bound is tight <ref:2502.06979#pg2,cover number by comparability graphs>.

The paper's improvements: Tom: The paper suggests several improvements to the existing understanding of these classes. They specifically focus on characterizing minimal non-word-representable graphs that contain an all-adjacent vertex by showing they are formed by adding an all-adjacent vertex to the word-representable minimal non-comparability graphs.

Jane: That characterization is formalized in Theorem thirteen which states that a graph is minimal non-word-representable if and only if removing one vertex leaves a minimal non-comparability graph that is word-representable.

Lu: Structurally, they show that for certain classes like outer-planar graphs or two trees or subcubic graphs or triangle-free planar graphs, the cover number by comparability graphs is at most two because these classes are all three colorable or have a chromatic number less than or equal to four <ref:2502.06979#pg2,cover number by comparability graphs>.

Meng: That connection between the coloring properties and the cover number being small, like two, seems like a strong structural constraint that we can use for practical graph analysis.

Lalam: They also show that Hasse diagrams with chromatic number alpha n to the power of one over four exist, which leads to a lower bound on the cover number by comparability graphs for triangle-free word-representable graphs being alpha log n.

Conclusion: Tom: So, wrapping up this discussion on "Word-representability and comparability: Minimal forbidden induced subgraphs and cover number bounds," the main implication is that they've completely characterized the set of minimal non-word-representable graphs containing an all-adjacent vertex.

Jane: They've also given us a solid understanding of how far word-representable graphs can be from being comparability graphs by showing that the O log n upper bound is tight, and providing tighter bounds for specific graph families.

Lu: The structural characterization of those minimal non-word-representable graphs, formalized in Theorem thirteen gives us a concrete condition—if removing one vertex leaves a word-representable minimal non-comparability graph—so we can test for this property efficiently.

Meng: From an engineering standpoint, knowing these precise structural conditions helps us predict when a graph will exhibit that high cover number behavior in our systems.

Lalam: To conclude, the paper provides the complete characterization of minimal non-word-representable graphs containing an all-adjacent vertex by showing they arise from word-representable minimal non-comparability graphs, and they also characterize four specific subclasses where the cover number by comparability graphs is at most two <ref:2502.06979#pg2,cover number by comparability graphs>.

Tom: That’s it for this paper on "Word-representability and comparability: Minimal forbidden induced subgraphs and cover number bounds." We've got a lot of structural information here to feed into our next set of model analysis.

Department of Computer Science and Engineering, Indian Institute of Technology Guwahati

cs.DM

Submitted: 2025-02-10

Updated: 2026-11-12

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 53/100

The gist: Word-representable graphs and comparability graphs are hereditary graph classes characterized by forbidden induced subgraphs…

Key concepts

Word-Representable Graph
A graph where adjacency can be defined by whether two vertices alternate in a specific word. This class includes many important graph types like circle graphs and subcubic graphs, and it is characterized by semi-transitive orientations.
Comparability Graph
A graph derived from a partial order where two vertices are connected if they are comparable (one can be ordered before the other). Comparability graphs form a subclass of word-representable graphs and are also defined by having edges admitting a transitive orientation.
Cover Number by Comparability Graphs
This measures how many comparability graphs are needed to cover all the edges of a given word-representable graph. The paper shows this number can be as high as O(log n) for certain graphs, proving the universal upper bound is asymptotically tight.
Minimal Non-Word-Representable Graph
These are the smallest graphs that cannot be represented by a word. The paper classifies these minimal non-comparability graphs, showing exactly which ones fail word-representability and characterizing those that include an all-adjacent vertex.

Terminology

Summary

Word-representable graphs and comparability graphs are hereditary graph classes characterized by forbidden induced subgraphs, and this paper precisely determines which minimal non-comparability graphs are also minimal non-word-representable, while also addressing the cover number of word-representable graphs by comparability graphs <ref:2502. p. 0

Where the paper says it

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 noncomparability graphs according to whether they are word-representable.

06979#pg2> The authors provide a complete description of minimal non-wordrepresentable graphs containing an all-adjacent vertex and establish asymptotic tightness for the universal O(log n) upper bound on the cover number by comparability graphs for word-representable graphs <ref:2502. p. 0
Where the paper says it

In this paper, we precisely determine which minimal non-comparability graphs are also minimal non-word-representable graphs by classifying minimal noncomparability graphs according to whether they are word-representable. As a consequence, we provide a complete description of minimal non-wordrepresentable graphs containing an all-adjacent vertex.

06979#pg14>.

Classification of Minimal Forbidden Structures

The paper resolves Problem 1 by classifying minimal non-comparability graphs into word-representable and non-word-representable cases, explicitly identifying the intersection between the classes of minimal non-comparability and minimal nonword-representable graphs <ref:2502.06979#pg12>. Specifically, Theorem 5 identifies the word-representable minimal non-comparability graphs as all graphs in families G1n, G2n, G3n, G5n, G6n, G7n, and G8n together with H2 through H11 and G92 <ref:2502. p. 9

Where the paper says it

, H11, together with G9 2 . Theorem 6 The minimal non-comparability graphs shown in Figure 4 that are not wordrepresentable are precisely the following: 1.

06979#pg11>. Conversely, Theorem 6 identifies the non-word-representable minimal non-comparability graphs as all graphs in families G4n and G9n for n ≥ 3, along with graph H1 <ref:2502. p. 9
Where the paper says it

The results are summarized in Theorems 5 and 6. Theorem 5 identifies the word-representable graphs among the collection, while Theorem 6 identifies the non-word-representable ones, which form the intersection of minimal non-comparability graphs with minimal non-word-representable graphs.

06979#pg13>.

Characterization of Minimal Non-Word-Representable Graphs

The authors characterize all minimal non-word-representable graphs that contain a universal (all-adjacent) vertex by showing that these graphs arise by adjoining an all-adjacent vertex to the minimal non-comparability graphs that are word-representable <ref:2502.06979#pg14>. This characterization is formalized in Theorem 13, which states that G is minimal non-word-representable if and only if H = G−x is a minimal non-comparability graph and H is word-representable <ref:2502. p. 7

Where the paper says it

4: List of all minimal non-comparability graphs 2. 3 Motivation for the Problems Both word-representable graphs and comparability graphs are hereditary graph classes and, as such, they admit a characterization in terms of forbidden induced subgraphs.

06979#pg15>.

Quantitative Bounds on Cover Numbers

The paper investigates the cover number of a word-representable graph by comparability graphs, denoted as covcomp(G), which quantifies how far G is from being a comparability graph <ref:2502.06979#pg14>. The authors demonstrate the existence of word-representable graphs on n vertices whose cover number by comparability graphs is Ω(log n), establishing that the universal O(log n) upper bound is asymptotically tight for this class <ref:2502. p. 0

Where the paper says it

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 Ω(log n), which establishes that the universal O(log n) upper bound is asymptotically tight for the class of word-representable graphs.

06979#pg14> Furthermore, for triangle-free circle graphs, they show that the cover number by comparability graphs is at most 3 and demonstrate that this bound is tight <ref:2502. p. 0
Where the paper says it

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 show that for any circle graph G with clique number ω(G), the cover number by comparability graphs is bounded by O(log ω(G)).

06979#pg15>.

Structural Properties of Specific Graph Classes

The work establishes several structural results regarding the cover number by comparability graphs for specific subclasses of word-representable graphs <ref:2502.06979#pg14>.

)& Theorem 14 states that for every graph G, the cover number of G by the class of graphs C = C = C is given by log χ(G) / log ω(G) <ref:2502. p. 2

Where the paper says it

More generally, we establish that for any circle graph G with clique number ω(G), the cover number by comparability graphs is bounded by O(log ω(G)). We identify four subclasses of word-representable graphs for which the cover number by comparability graphs is at most 2 for every graph in the class.

06979#pg14>. This leads to a lower bound covcomp(G) ≥ covperf(G) ≥ log χ(G) / log ω(G) <ref:2502. p. 0
Where the paper says it

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 Ω(log n), which establishes that the universal O(log n) upper bound is asymptotically tight for the class of word-representable graphs.

06979#pg14>. For circle graphs, the upper bound is O(log ω(G)) <ref:2502. p. 0
Where the paper says it

We demonstrate the existence of word-representable graphs on n vertices whose cover number by comparability graphs is Ω(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.

06979#pg15>. 3.

**)& Theorem 19 shows that the graphs in classes such as outer-planar graphs, 2-trees, sub-cubic graphs, and triangle-free planar graphs can be expressed as the union of at most two comparability graphs <ref:2502. p. 5

Where the paper says it

Definition 4 A class X of graphs is called hereditary if, for every graph G ∈ X, every induced subgraph of G also belongs to X. Examples of hereditary graph classes include planar graphs, comparability graphs, and word-representable graphs [3].

06979#pg15>. This is because these classes are all 3-colorable or satisfy χ(G) ≤ 4, implying that the number of required bipartite graphs to cover the edges is at most 2, and since bipartite graphs are comparability graphs, this implies a cover number of at most 2 <ref:2502. p. 0
Where the paper says it

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. 1 arXiv:2502.

06979#pg15>. **

**)& The existence of Hasse diagrams with chromatic number χ(G) = Ω(n(1/4)) is proven, which leads to the result that the cover number by comparability graphs for triangle-free word-representable graphs is Ω(log n) <ref:2502. p. 0

Where the paper says it

We demonstrate the existence of word-representable graphs on n vertices whose cover number by comparability graphs is Ω(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.

06979#pg15>. **

**)& The paper identifies four subclasses of word-representable graphs for which every graph in these classes has a cover number by comparability graphs of at most 2 <ref:2502. p. 0

Where the paper says it

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. 1 arXiv:2502.

06979#pg15>. **

Concluding Characterization

The concluding remarks summarize the findings, stating that the intersection of minimal non-comparability and minimal non-word-representable graphs consists of two infinite families, G9n for n ≥ 3 and G4n, together with H1 <ref:2502.06979#pg15>. This result completely characterizes the set of minimal non-word-representable graphs containing an all-adjacent vertex <ref:2502. p. 0

Where the paper says it

In this paper, we precisely determine which minimal non-comparability graphs are also minimal non-word-representable graphs by classifying minimal noncomparability graphs according to whether they are word-representable. As a consequence, we provide a complete description of minimal non-wordrepresentable graphs containing an all-adjacent vertex.

06979#pg15>. The paper successfully combines structural classification with quantitative analysis of covering parameters to provide a deep understanding of the relationship between word-representable and comparability graphs <ref:2502. p. 8
Where the paper says it

While such comparisons are inherently qualitative, it is also natural to seek quantitative measures of the relationship between the two classes. This motivates the study of covering parameters, in particular the minimum number of comparability graphs whose union covers the edges of a given graph.

06979#pg15>.

References

[1] Kitaev, S., Seif, S.: Word problem of the perkins semigroup via directed acyclic graphs <ref:2502. p. 4

Where the paper says it

Word-representable graphs admit a characterization via the notion of a semitransitive orientation, defined below. Definition 3 A graph G is semi-transitive if it admits an acyclic orientation such that for every directed path v1 → v2 → · · · → vk, either v1 ̸→ vk, or vi → vj exists for all 1 ≤ i < j ≤ k.

06979#pg15>

[3] Kitaev, S., Lozin, V.: Words and Graphs <ref:2502. p. 0

Where the paper says it

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. 1 arXiv:2502.

06979#pg15>

[8] Kenkireth, B.G., Sajith, G. p. 0

Where the paper says it

in; Contributing authors: ben@iitg. in; sajith@iitg.

, Sasidharan, S.: On word-representability of minimal non-comparability graphs <ref:2502. p. 9
Where the paper says it

3 Classification of Minimal Non-Comparability Graphs with Respect to Word-Representability Figure 4 presents the complete set of minimal non-comparability graphs. This collection consists of two types: individual graphs Hi and infinite families of graphs Gi n parameterized by n.

06979#pg15>

[13] Davies, J.: Improved bounds for colouring circle graphs <ref:2502. p. 0

Where the paper says it

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. 1 arXiv:2502.

06979#pg15>

[14] Harary, F., Hsu, D., Miller, Z.: The biparticity of a graph <ref:2502. p. 0

Where the paper says it

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. 1 arXiv:2502.

06979#pg15>

[15] Kostochka, A.V.: Upper bounds on the chromatic number of graphs <ref:2502. p. 0

Where the paper says it

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. 1 arXiv:2502.

06979#pg15>

[16] Ageev, A.A.: A triangle-free circle graph with chromatic number 5 <ref:2502. p. 0

Where the paper says it

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 show that for any circle graph G with clique number ω(G), the cover number by comparability graphs is bounded by O(log ω(G)).

06979#pg15>

[17] Suk, A., Tomon, I.: Hasse diagrams with large chromatic number <ref:2502. p. 0

Where the paper says it

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. 1 arXiv:2502.

06979#pg15>

[18] There exist word-representable graphs on n vertices whose cover number by comparability graphs is Ω(log n) <ref:2502.06979#pg15>

[19] The graphs in each of the following classes of word-representable graphs can be expressed as the union of at most two comparability graphs <ref:2502.06979#pg15>

--- Page 1 ---

Word-representability and comparability: Minimal forbidden induced subgraphs and cover number bounds <ref:2502.06979#pg15>

Benny George Kenkireth, Gopalan Sajith, Sreyas Sasidharan <ref:2502.06979#pg15>

**/Department of Computer Science and Engineering, Indian Institute of Technology Guwahati, Guwahati, India <ref:2502.06979#pg15> **

E-mail(s): sreyas.s@iitg.ac.in; Contributing authors: ben@iitg. p. 0

Where the paper says it

E-mail(s): sreyas. in; Contributing authors: ben@iitg.

ac.in; sajith@iitg. p. 0
Where the paper says it

in; Contributing authors: ben@iitg. in; sajith@iitg.

ac.in <ref:2502. p. 0
Where the paper says it

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. 1 arXiv:2502.

06979#pg15>

Abstract

Word-representable graphs, characterized by the existence of a semi-transitive orientation, form a well-studied class of graphs <ref:2502.06979#pg15>. Comparability graphs form another well-studied class and constitute a subclass of word-representable graphs <ref:2502. p. 0

Where the paper says it

in; 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.

06979#pg15>. Both classes are hereditary and admit characterizations in terms of minimal forbidden induced subgraphs <ref:2502. p. 0
Where the paper says it

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.

06979#pg15>. While the minimal forbidden induced subgraphs for comparability graphs are completely characterized, the corresponding characterization for word-representable graphs remains open <ref:2502. p. 0
Where the paper says it

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.

06979#pg15>. In this paper, we precisely determine which minimal non-comparability graphs are also minimal non-word-representable graphs by classifying minimal noncomparability graphs according to whether they are word-representable <ref:2502. p. 0
Where the paper says it

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 noncomparability graphs according to whether they are word-representable.

06979#pg15>. As a consequence, we provide a complete description of minimal non-wordrepresentable graphs containing an all-adjacent vertex <ref:2502. p. 0
Where the paper says it

In this paper, we precisely determine which minimal non-comparability graphs are also minimal non-word-representable graphs by classifying minimal noncomparability graphs according to whether they are word-representable. As a consequence, we provide a complete description of minimal non-wordrepresentable graphs containing an all-adjacent vertex.

06979#pg15>. We also address an open problem posed by Kenkireth et al. p. 0
Where the paper says it

As a consequence, we provide a complete description of minimal non-wordrepresentable 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 <ref:2502. p. 0
Where the paper says it

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. 1 arXiv:2502.

06979#pg15>. We demonstrate the existence of word-representable graphs on n vertices whose cover number by comparability graphs is Ω(log n), which establishes that the universal O(log n) upper bound is asymptotically tight for the class of word-representable graphs <ref:2502. p. 0
Where the paper says it

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 Ω(log n), which establishes that the universal O(log n) upper bound is asymptotically tight for the class of word-representable graphs.

06979#pg15>. 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 <ref:2502. p. 0
Where the paper says it

We demonstrate the existence of word-representable graphs on n vertices whose cover number by comparability graphs is Ω(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.

06979#pg15>. More generally, we show that for any circle graph G with clique number ω(G), the cover number by comparability graphs is bounded by O(log ω(G)) <ref:2502. p. 0
Where the paper says it

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 show that for any circle graph G with clique number ω(G), the cover number by comparability graphs is bounded by O(log ω(G)).

06979#pg15>. 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 <ref:2502. p. 0
Where the paper says it

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. 1 arXiv:2502.

06979#pg15>.

--- Page 3 ---

Keywords: word-representable graph, comparability graph, minimal non-word-representable graph, minimal non-comparability graph, semi-transitive orientation, cover number by comparability graphs <ref:2502.06979#pg15>

--- Page 4 ---

1 Introduction

Word-representable graphs have been extensively studied <ref:2502.06979#pg15>. The notion was introduced by Kitaev [1] <ref:2502. p. 1

Where the paper says it

Keywords: word-representable graph, comparability graph, minimal non-word-representable graph, minimal non-comparability graph, semi-transitive orientation, cover number by comparability graphs, circle graphs 1 Introduction Word-representable graphs have been extensively studied. The notion was introduced by Kitaev [1].

06979#pg15>. A graph is called word-representable if there exists a word over its vertex set such that two vertices are adjacent in the graph if and only if they alternate in the word <ref:2502. p. 1
Where the paper says it

The notion was introduced by Kitaev [1]. A graph is called word-representable if there exists a word over its vertex set such that two vertices are adjacent in the graph if and only if they alternate in the word.

06979#pg15>. The class of word-representable graphs encompasses many well-known graph families, including 3-colorable graphs, comparability graphs, subcubic graphs, and circle graphs [2, 3] <ref:2502. p. 1
Where the paper says it

A graph is called word-representable if there exists a word over its vertex set such that two vertices are adjacent in the graph if and only if they alternate in the word. The class of word-representable graphs encompasses many well-known graph families, including 3-colorable graphs, comparability graphs, subcubic graphs, and circle graphs [2, 3].

06979#pg15>. Word-representable graphs admit a complete characterization in terms of semi-transitive orientations <ref:2502. p. 1
Where the paper says it

The class of word-representable graphs encompasses many well-known graph families, including 3-colorable graphs, comparability graphs, subcubic graphs, and circle graphs [2, 3]. Word-representable graphs admit a complete characterization in terms of semi-transitive orientations: a graph is word-representable if and only if it has such an orientation.

06979#pg15>.

--- Page 5 ---

Word-representable graphs form a hereditary class; i.e., every induced subgraph of a word-representable graph is itself word-representable <ref:2502. p. 1

Where the paper says it

Word-representable graphs form a hereditary class; i. , every induced subgraph of a word-representable graph is itself word-representable.

06979#pg15>. Every such class can be characterized by forbidden induced subgraphs and has a unique set of minimal ones, here, in the context of word-representability, called minimal non-word-representable graphs <ref:2502. p. 1
Where the paper says it

, every induced subgraph of a word-representable graph is itself word-representable. Every such class can be characterized by forbidden induced subgraphs and has a unique set of minimal ones, here, in the context of word-representability, called minimal non-word-representable graphs.

06979#pg15>. Despite substantial progress (see, e. p. 1
Where the paper says it

Every such class can be characterized by forbidden induced subgraphs and has a unique set of minimal ones, here, in the context of word-representability, called minimal non-word-representable graphs. Despite substantial progress (see, e.

g., [4–6]), a complete description of the minimal non-word-representable graphs remains open <ref:2502. p. 1
Where the paper says it

Despite substantial progress (see, e. , [4–6]), a complete description of the minimal non-word-representable graphs remains open.

06979#pg15>. Comparability graphs form an important subclass of word-representable graphs <ref:2502. p. 1
Where the paper says it

, [4–6]), a complete description of the minimal non-word-representable graphs remains open. Comparability graphs form an important subclass of word-representable graphs.

06979#pg15>. They constitute a classical family of graphs arising from partial orders: a graph is a comparability graph if its vertices can be endowed with a partial order such that two vertices are adjacent precisely when they are comparable <ref:2502. p. 1
Where the paper says it

Comparability graphs form an important subclass of word-representable graphs. They constitute a classical family of graphs arising from partial orders: a graph is a comparability graph if its vertices can be endowed with a partial order such that two vertices are adjacent precisely when they are comparable.

06979#pg15>. A graph is also a comparability graph if its edges admit a transitive orientation <ref:2502. p. 1
Where the paper says it

They constitute a classical family of graphs arising from partial orders: a graph is a comparability graph if its vertices can be endowed with a partial order such that two vertices are adjacent precisely when they are comparable. Equivalently, a graph is a comparability graph if its edges admit a transitive orientation.

06979#pg15>.

--- Page 6 ---

Since comparability graphs form a subclass of word-representable graphs, it is natural to ask whether there exist graphs that are simultaneously minimal noncomparability and minimal non-word-representable, and to identify them <ref:2502.06979#pg15>. In this paper, we answer this question completely <ref:2502. p. 1

Where the paper says it

Since comparability graphs form a subclass of word-representable graphs, it is natural to ask whether there exist graphs that are simultaneously minimal noncomparability and minimal non-word-representable, and to identify them. In this paper, we answer this question completely.

06979#pg15>. By classifying minimal non-comparability graphs into word-representable and non-word-representable cases, we determine exactly which of them are minimal non-word-representable <ref:2502. p. 1
Where the paper says it

In this paper, we answer this question completely. By classifying minimal non-comparability graphs into word-representable and non-word-representable cases, we determine exactly which of them are minimal non-word-representable.

06979#pg15>. This classification also yields a complete list of minimal non-word-representable graphs containing a universal (all-adjacent) vertex <ref:2502. p. 1
Where the paper says it

By classifying minimal non-comparability graphs into word-representable and non-word-representable cases, we determine exactly which of them are minimal non-word-representable. This classification also yields a complete list of minimal non-word-representable graphs containing a universal (all-adjacent) vertex, thereby identifying many infinite families of graphs that are minimal non-word-representable.

06979#pg15>.

--- Page 7 ---

In the broader context of comparing wordrepresentable graphs and comparability graphs, we also consider the problem of determining the minimum number of comparability graphs whose union forms a given word-representable graph, which was an open problem posed in [8] <ref:2502.06979#pg15>. More formally, given a word-representable graph G, we consider the smallest integer k for which there exist comparability graphs G1,. p. 2

Where the paper says it

word-representable graph, which was an open problem posed in [8]. More formally, given a word-representable graph G, we consider the smallest integer k for which there exist comparability graphs G1, G2, .

.., Gk such that every edge of G is contained in at least one of these graphs <ref:2502. p. 2
Where the paper says it

More formally, given a word-representable graph G, we consider the smallest integer k for which there exist comparability graphs G1, G2, . , Gk such that every edge of G is contained in at least one of these graphs.

06979#pg15>. This integer k is referred to as the cover number of G by comparability graphs <ref:2502. p. 2
Where the paper says it

That is, the edge set of G is the union of the edge sets of G1, . This integer k is referred to as the cover number of G by comparability graphs.

06979#pg15>.

--- Page 8 ---

Studying both aspects—identifying common minimal forbidden induced subgraphs and analyzing the cover number—provides insight into the structural relationship between these two graph classes <ref:2502.06979#pg15>. Since comparability graphs form a subclass of word-representable graphs, both problems are natural and contribute to a deeper understanding of how these classes are related <ref:2502. p. 2

Where the paper says it

Studying both aspects—identifying common minimal forbidden induced subgraphs and analyzing the cover number—provides insight into the structural relationship between these two graph classes. Since comparability graphs form a subclass of word-representable graphs, both problems are natural and contribute to a deeper understanding of how these classes are related.

06979#pg15>.

--- Page 9 ---

In this paper, we investigate the following problems <ref:2502.06979#pg15>. Problem 1 Determine which minimal non-comparability graphs are also minimal non-wordrepresentable graphs <ref:2502. p. 2

Where the paper says it

In this paper, we investigate the following problems. Problem 1 Determine which minimal non-comparability graphs are also minimal non-wordrepresentable graphs.

06979#pg15>. Problem 2 For an arbitrary word-representable graph, determine its cover number by comparability graphs <ref:2502. p. 2
Where the paper says it

Problem 1 Determine which minimal non-comparability graphs are also minimal non-wordrepresentable graphs. Problem 2 For an arbitrary word-representable graph, determine its cover number by comparability graphs.

06979#pg15>.

--- Page 10 ---

Our contributions provide a complete classification of minimal non-comparability graphs into word-representable and non-word-representable graphs, explicitly identifying the intersection between the classes of minimal non-comparability and minimal nonword-representable graphs <ref:2502.06979#pg15>. We also characterize all minimal non-word-representable graphs that contain a universal (all-adjacent) vertex <ref:2502. p. 2

Where the paper says it

We provide a complete classification of minimal non-comparability graphs into word-representable and non-word-representable graphs, explicitly identifying the intersection between the classes of minimal non-comparability and minimal nonword-representable graphs. We characterize all minimal non-word-representable graphs that contain a universal (all-adjacent) vertex.

p. 2
Where the paper says it

We provide a complete classification of minimal non-comparability graphs into word-representable and non-word-representable graphs, explicitly identifying the intersection between the classes of minimal non-comparability and minimal nonword-representable graphs. We characterize all minimal non-word-representable graphs that contain a universal (all-adjacent) vertex.

06979#pg15>.

--- Page 11 ---

We provide structural results for Problem 2, including demonstrating the existence of word-representable graphs on n vertices whose cover number by comparability graphs is Ω(log n), which establishes that this upper bound is asymptotically tight for the class of word-representable graphs <ref:2502.06979#pg15>.

--- Page 12 ---

Our contributions include demonstrating the existence of word-representable graphs on n vertices whose cover number by comparability graphs is Ω(log n), which establishes that this upper bound is asymptotically tight for the class of word-representable graphs <ref:2502.06979#pg15>.

--- Page 13 ---

We also address an open problem posed in [8] concerning the cover number of word-representable graphs by comparability graphs <ref:2502. p. 0

Where the paper says it

We also address an open problem posed by Kenkireth et al. concerning the cover number of word-representable graphs by comparability graphs.

06979#pg15>. We also address an open problem posed in [8] concerning the cover number of word-representable graphs by comparability graphs <ref:2502.06979#pg15>.

--- Page 14 ---

We also address an open problem posed in [8] concerning the cover number of word-representable graphs by comparability graphs <ref:2502.06979#pg15>.

--- Page 15 ---

The remainder of the paper is organized as follows <ref:2502.06979#pg15>. In Section 3, we address Problem 1 by classifying minimal non-comparability graphs according to whether they are word-representable <ref:2502. p. 3

Where the paper says it

classifying minimal non-comparability graphs according to whether they are wordrepresentable. In Section 4, we investigate Problem 2 concerning coverings of wordrepresentable graphs by comparability graphs.

06979#pg15>. In Section 4, we investigate Problem 2 concerning coverings of wordrepresentable graphs by comparability graphs <ref:2502. p. 3
Where the paper says it

classifying minimal non-comparability graphs according to whether they are wordrepresentable. In Section 4, we investigate Problem 2 concerning coverings of wordrepresentable graphs by comparability graphs.

p. 3
Where the paper says it

classifying minimal non-comparability graphs according to whether they are wordrepresentable. In Section 4, we investigate Problem 2 concerning coverings of wordrepresentable graphs by comparability graphs.

p. 3
Where the paper says it

classifying minimal non-comparability graphs according to whether they are wordrepresentable. In Section 4, we investigate Problem 2 concerning coverings of wordrepresentable graphs by comparability graphs.

p. 3
Where the paper says it

classifying minimal non-comparability graphs according to whether they are wordrepresentable. In Section 4, we investigate Problem 2 concerning coverings of wordrepresentable graphs by comparability graphs.

p. 3
Where the paper says it

classifying minimal non-comparability graphs according to whether they are wordrepresentable. In Section 4, we investigate Problem 2 concerning coverings of wordrepresentable graphs by comparability graphs.

06979#pg15>.

--- Page 16 ---

We provide a complete classification of minimal non-comparability graphs into word-representable and non-word-representable graphs, explicitly identifying the intersection between the classes of minimal non-comparability and minimal nonword-representable graphs <ref:2502.06979#pg15>. We also characterize all minimal non-word-representable graphs that contain a universal (all-adjacent) vertex <ref:2502.06979#pg15>.

Pruning redundant reasoning tokens

The remainder of the paper is organized as follows <ref:2502.06979#pg15> In Section 3, we address Problem 1 by classifying minimal non-comparability graphs according to whether they are word-representable <ref:2502. p. 3

Where the paper says it

classifying minimal non-comparability graphs according to whether they are wordrepresentable. In Section 4, we investigate Problem 2 concerning coverings of wordrepresentable graphs by comparability graphs.

p. 3
Where the paper says it

classifying minimal non-comparability graphs according to whether they are wordrepresentable. In Section 4, we investigate Problem 2 concerning coverings of wordrepresentable graphs by comparability graphs.

p. 3
Where the paper says it

classifying minimal non-comparability graphs according to whether they are wordrepresentable. In Section 4, we investigate Problem 2 concerning coverings of wordrepresentable graphs by comparability graphs.

p. 3
Where the paper says it

classifying minimal non-comparability graphs according to whether they are wordrepresentable. In Section 4, we investigate Problem 2 concerning coverings of wordrepresentable graphs by comparability graphs.

06979#pg15>. In Section 4, we investigate Problem 2 concerning coverings of wordrepresentable graphs by comparability graphs <ref:2502.06979#pg15>

How the training signal is built

The remainder of the paper is organized as follows <ref:2502.06979#pg15> In Section 3, we address Problem 1 by classifying minimal non-comparability graphs according to whether they are word-representable <ref:2502.06979#pg15>. In Section 4, we investigate Problem 2 concerning coverings of wordrepresentable graphs by comparability graphs <ref:2502.06979#pg15>

Where the gains come from

The remainder of the paper is organized as follows <ref:2502.06979#pg15> In Section 3, we address Problem 1 by classifying minimal non-comparability graphs according to whether they are word-representable <ref:2502.06979#pg15>. In Section 4, we investigate Problem 2 concerning coverings of wordrepresentable graphs by comparability graphs <ref:2502.06979#pg15>

The remainder of the paper is organized as follows <ref:2502.06979#pg15> In Section 3, we address Problem 1 by classifying minimal non-comparability graphs according to whether they are word-representable <ref:2502.06979#pg15>. In Section 4, we investigate Problem 2 concerning coverings of wordrepresentable graphs by comparability graphs <ref:2502.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Classification of minimal non-comparability graphs by word-representability enables AI to precisely identify which minimal forbidden induced subgraphs are also minimal non-word-representable graphs, resolving an open problem for this graph class.

  2. Characterization of all minimal non-word-representable graphs containing an all-adjacent vertex allows AI to completely describe these structures, identifying many infinite families of graphs that are minimal non-word-representable.

  3. The determination of the cover number by comparability graphs for any word-representable graph allows AI to quantify the distance of G from the class of comparability graphs and establish asymptotic tightness for the universal O(log n) upper bound.

  4. For circle graphs, AI can determine that the cover number by comparability graphs is at most 3, providing a specific quantitative bound for this subclass and demonstrating its tightness.

  5. The establishment of an upper bound of O(log omega G) for the cover number by comparability graphs of any circle graph G allows AI to predict that for any circle graph G with clique number omega(G), the cover number by comparability graphs is bounded by O(log omega(G)).

  6. Identification of four subclasses of word-representable graphs where the cover number by comparability graphs is at most 2 for every graph in the class allows AI to quickly assess if a given graph belongs to these highly structured classes.

  7. The characterization of minimal non-word-representable graphs with an all-adjacent vertex, formalized by Theorem 13, provides a complete condition: H is a minimal non-comparability graph and H is word-representable, enabling AI to test for this property efficiently.

  8. AI can use the derived lower bound covcomp(G) >= log chi(G) / log omega(G) to establish that the O(log n) upper bound on the cover number by comparability graphs is asymptotically tight for the class of word-representable graphs using Hasse diagrams as counterexamples.

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 Ω(n), which establishes that the universal O(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 show that for any circle graph G with clique number ω(G), the cover number by comparability graphs is bounded by O(ω(G)). 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.

Related papers