Word-representability and comparability: Minimal forbidden induced subgraphs and cover number bounds
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 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. 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.Where the paper says it
Where the paper says it
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 , 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. 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.Where the paper says it
Where the paper says it
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 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.Where the paper says it
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 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. 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)).Where the paper says it
Where the paper says it
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 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
**)& 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 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]. 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.Where the paper says it
Where the paper says it
**)& 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 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.Where the paper says it
**)& 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 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.Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
References
[1] Kitaev, S., Seif, S.: Word problem of the perkins semigroup via directed acyclic graphs <ref:2502. p. 4 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.Where the paper says it
[3] Kitaev, S., Lozin, V.: Words and Graphs <ref:2502. p. 0 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.Where the paper says it
[8] Kenkireth, B.G., Sajith, G. p. 0 in;
Contributing authors: ben@iitg. in; sajith@iitg. 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.Where the paper says it
Where the paper says it
[13] Davies, J.: Improved bounds for colouring circle graphs <ref:2502. p. 0 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.Where the paper says it
[14] Harary, F., Hsu, D., Miller, Z.: The biparticity of a graph <ref:2502. p. 0 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.Where the paper says it
[15] Kostochka, A.V.: Upper bounds on the chromatic number of graphs <ref:2502. p. 0 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.Where the paper says it
[16] Ageev, A.A.: A triangle-free circle graph with chromatic number 5 <ref:2502. p. 0 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)).Where the paper says it
[17] Suk, A., Tomon, I.: Hasse diagrams with large chromatic number <ref:2502. p. 0 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.Where the paper says it
[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 E-mail(s): sreyas. in;
Contributing authors: ben@iitg. in;
Contributing authors: ben@iitg. in; sajith@iitg. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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. 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. 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. 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. 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. 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. 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. 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. 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)). 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
--- 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 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]. 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. 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]. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
--- 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 Word-representable graphs form a hereditary class; i. , every induced subgraph
of a word-representable graph is itself word-representable. , 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. 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. Despite substantial progress (see, e. , [4–6]), a complete description of the
minimal non-word-representable graphs remains open. , [4–6]), a complete description of the
minimal non-word-representable graphs remains open. Comparability graphs form an important subclass of word-representable graphs. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
--- 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 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
--- 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 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, . 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
--- 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 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.Where the paper says it
--- 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 In this paper, we investigate the following problems. Problem 1
Determine which minimal non-comparability graphs are also minimal non-wordrepresentable graphs. 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.Where the paper says it
Where the paper says it
--- 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 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. 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.Where the paper says it
Where the paper says it
--- 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 We also address an open problem posed by Kenkireth et al. concerning the cover
number of word-representable graphs by comparability graphs.Where the paper says it
--- 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 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. 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. 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. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
--- 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 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. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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
-
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.
-
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.
-
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. -
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. -
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)).
-
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. -
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. -
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
- Low-Temperature Sampling via Equilibrium Disagreements
- An Improved Bound for Testing k-Colorability
- Temporal Cliques Admit Linear Spanners
- Multiway Partition is FPT for Connectivity Functions
- Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
- Constrained intersection representations and forbidden patterns