REVIEW 1 cited by
Representation Number of Word-Representable Split Graphs
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
A split graph is a graph whose vertex set can be partitioned into a clique and an independent set. The word-representability of split graphs was studied in a series of papers in the literature, and the class of word-representable split graphs was characterized through semi-transitive orientation. Nonetheless, the representation number of this class of graphs is still not known. In general, determining the representation number of a word-representable graph is an NP-complete problem. In this work, through an algorithmic procedure, we show that the representation number of the class of word-representable split graphs is at most three. Further, we characterize the class of word-representable split graphs as well as the class of split comparability graphs which have representation number exactly three.
Forward citations
Cited by 1 Pith paper
-
On the Conjecture of the Representation Number of Bipartite Graphs
Every bipartite graph is (1+ceil(m/2))-representable, improving to ceil(m/2) when the smaller part has odd size, settling the Glen et al. conjecture except for equal-even bipartitions.
Discussion (0). Continue with ORCID to comment.