|
===Representation of split graphs===
Word-representation of [[Split graph|split graphs]] is studied in <ref name="KLMW2017">[[arxiv:1709.09725|S. Kitaev, Y. Long, J. Ma, H. Wu. Word-representability of split graphs, arXiv:1709.09725 (2017).]]</ref> <ref name="CKS2019">[[arXiv:1909.09471|T. Z. Q. Chen, S. Kitaev, and A. Saito. Representing split graphs by words, arXiv:1909.09471]]</ref>. In particular, <ref name="KLMW2017" /> offers a characterisation in terms of forbidden induced subgraphs of word-representable split graphs in which vertices in the independent set are of degree at most 2, or the size of the clique is 4, while a computational characterisation of word-representable split graphs with the clique of size 5 is given in <ref name="CKS2019" />. Also, necessary and sufficient conditions for an orientation of a split graph to be semi-transitive are given in <ref name="KLMW2017" />, while in <ref name="CKS2019" /> [[Threshold graph|threshold graphs]] are shown to be word-representable and the split graphs are used 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, which solved a long-standing open problem.
===Graphs representable by pattern avoiding words===
==Generalisations==
A number of generalisations <ref name="JKPR2015">[https://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p53 M. Jones, S. Kitaev, A. Pyatkin, and J. Remmel. Representing Graphs via Pattern Avoiding Words, Electron. J. Combin. 22 (2), Res. Pap. P2.53, 1−20 (2015).]</ref> <ref name="GJ2019">[https://www.lehmanns.de/shop/mathematik-informatik/48968161-9783030287955-combinatorics-on-words M. Gaetz and C. Ji. Enumeration and extensions of word-representable graphs. Lecture Notes in Computer Science 11682 (2019) 180−192. In R. Mercas, D. Reidenbach (Eds) Combinatorics on Words. WORDS 2019.]</ref> <ref name="GJ2019-2">[[arXiv:1909.00019|M. Gaetz and C. Ji. Enumeration and Extensions of Word-representants, arXiv:1909.00019.]]</ref> of the notion of a word-representable graph are based on the observation by [https://www.math.ucsd.edu/memorials/jeffrey-remmel/ Jeff Remmel] that non-edges are defined by occurrences of the pattern 11 (two consecutive equal letters) in a word representing a graph, while edges are defined by avoidance of this pattern. For example, instead of the pattern 11, one can use the pattern 112, or the pattern, 1212, or any other binary pattern where the assumption that the alphabet is ordered can be made so that a letter in a word corresponding to 1 in the pattern is less than that corresponding to 2 in the pattern. Letting ''u'' be an ordered binary pattern we thus get the notion of a '''''u''-representable graph'''. So, word-representable graphs are just the class of 11-representable graphs. Intriguingly, '''any graph''' can be ''u''-represented assuming ''u'' is of length at least 3 <ref name="K2017">[https://onlinelibrary.wiley.com/doi/full/10.1002/jgt.22097 S. Kitaev. Existence of u-representation of graphs, Journal of Graph Theory 85 (2017) 3, 661−668.]</ref>.
Another way to generalise the notion of a word-representable graph, again suggested by [https://www.math.ucsd.edu/memorials/jeffrey-remmel/ Jeff Remmel], is to introduce the "degree of tolerance" ''k'' for occurrences of a pattern ''p'' defining edges/non-edges. That is, we can say that if there are up to ''k'' occurrence of ''p'' formed by letters ''a'' and ''b'', then there is an edge between ''a'' and ''b''. This gives the notion of a ''k''-''p''-representable graph, and ''k''-11-representable graphs are studied in <ref name="CKKK2019">[[arxiv:1803.01055|G.-S. Cheon, J. Kim, M. Kim, and A. Pyatkin. On ''k''-11-representable graphs. J. Combin. 10 (2019) 3, 491−513.]]</ref>. Note that 0-11-representable graphs are precisely word-representable graphs. The key results in <ref name="CKKK2019" /> are that '''any''' graph is 2-11-representable and that word-representable graphs are a proper subclass of 1-11-representable graphs. Whether or not any graph is 1-11-representable is a challenging open problem.
|
