Geodesic
Representing Split Graphs by Words
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1263-1280 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

There is a long line of research in the literature dedicated to word-representable graphs, which generalize several important classes of graphs. However, not much is known about word-representability of split graphs, another important class of graphs. In this paper, we show that threshold graphs, a subclass of split graphs, are word-representable. Further, we prove a number of general theorems on word-representable split graphs, and use them to characterize computationally such graphs with cliques of size 5 in terms of nine forbidden subgraphs, thus extending the known characterization for word-representable split graphs with cliques of size 4. Moreover, we use split graphs, and also provide an alternative solution, to show that gluing two word-representable graphs in any clique of size at least 2 may, or may not, result in a word-representable graph. The two surprisingly simple solutions provided by us answer a question that was open for about ten years.
Keywords: split graph, word-representability, semi-transitive orientation 
@article{DMGT_2022_42_4_a14,
     author = {Chen, Herman Z.Q. and Kitaev, Sergey and Saito, Akira},
     title = {Representing {Split} {Graphs} by {Words}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1263--1280},
     year = {2022},
     volume = {42},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a14/}
}
TY  - JOUR
AU  - Chen, Herman Z.Q.
AU  - Kitaev, Sergey
AU  - Saito, Akira
TI  - Representing Split Graphs by Words
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 1263
EP  - 1280
VL  - 42
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a14/
LA  - en
ID  - DMGT_2022_42_4_a14
ER  - 
%0 Journal Article
%A Chen, Herman Z.Q.
%A Kitaev, Sergey
%A Saito, Akira
%T Representing Split Graphs by Words
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 1263-1280
%V 42
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a14/
%G en
%F DMGT_2022_42_4_a14
Chen, Herman Z.Q.; Kitaev, Sergey; Saito, Akira. Representing Split Graphs by Words. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1263-1280. http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a14/

[1] V. Chvátal and P.L. Hammer, Aggregation of inequalities in integer programming, in: Ann. Discrete Math. 1 (1977), P.L. Hammer, E.L. Johnson, B.H. Korte and G.L. Nemhauser (Ed(s)), (Studies in Integer Programming (Proc. Worksh. Bonn, 1975) 145–162. https://doi.org/10.1016/S0167-5060(08)70731-3

[2] S. Foldes and P.L. Hammer, Split graphs, in: Proc. Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. XIX (1977), (Louisiana State Univ., Baton Rouge, 1977) 311–315.

[3] M. Glen, Software . http://personal.strath.ac.uk/sergey.kitaev/word-representable-graphs.html

[4] M. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Elsevier Inc., 1980). https://doi.org/10.1016/B978-0-12-289260-8.50010-8

[5] M.M. Halldórsson, S. Kitaev and A. Pyatkin, Semi-transitive orientations and word-representable graphs, Discrete Appl. Math. 201 (2016) 164–171. https://doi.org/10.1016/j.dam.2015.07.033

[6] S. Kitaev, A comprehensive introduction to the theory of word-representable graphs, in: Developments in Language Theory, DLT 2017, E. Charlier, J. Leroy and M. Rigo (Ed(s)), Lecture Notes in Comput. Sci. 10396 (2017) 36–67. https://doi.org/10.1007/978-3-319-62809-7_2

[7] S. Kitaev, Y. Long, J. Ma and H. Wu, Word-representability of split graphs . arXiv:1709.09725

[8] S. Kitaev and V. Lozin, Words and Graphs (Springer, 2015). https://doi.org/10.1007/978-3-319-25859-1

[9] N.V.R. Mahadev and U.N. Peled, Threshold Graphs and Related Topics (Elsevier, 1995).