Word-representability of split graphs

Kitaev, Sergey and Long, Yangjing and Ma, Jun and Wu, Hehui (2020) Word-representability of split graphs. Journal of Combinatorics. ISSN 2156-3527 (In Press)

[thumbnail of Kitaev-etal-JC-2020-Word-representability-of-split-graphs]
Preview
Text (Kitaev-etal-JC-2020-Word-representability-of-split-graphs)
Kitaev_etal_JC_2020_Word_representability_of_split_graphs.pdf
Accepted Author Manuscript

Download (326kB)| Preview

    Abstract

    Two letters x and y alternate in a word w if after deleting in wall letters but the copies of x and y we either obtain a word xyxy (of even or odd length) or a word yxyx (of even or odd length). Agraph G = (V;E) is word-representable if there exists a word w overthe alphabet V such that letters x and y alternate in w if and only ifxy 2 E. It is known that a graph is word-representable if and only ifit admits a certain orientation called semi-transitive orientation.Word-representable graphs generalize several important classes ofgraphs such as 3-colorable graphs, circle graphs, and comparabilitygraphs. There is a long line of research in the literature dedicatedto word-representable graphs. However, almost nothing is known onword-representability of split graphs, that is, graphs in which the ver-tices can be partitioned into a clique and an independent set. In thispaper, we shed a light to this direction. In particular, we character-ize in terms of forbidden subgraphs word-representable split graphsin which vertices in the independent set are of degree at most 2, orthe size of the clique is 4. Moreover, we give necessary and sucientconditions for an orientation of a split graph to be semi-transitive.

    ORCID iDs

    Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647, Long, Yangjing, Ma, Jun and Wu, Hehui;