Existence of μ-representation of graphs

Kitaev, Sergey (2017) Existence of μ-representation of graphs. Journal of Graph Theory, 85 (3). pp. 661-668. ISSN 1097-0118 (https://doi.org/10.1002/jgt.22097)

[thumbnail of Kitaev-JGT2016-Existence-of-μ-representation-of-graphs]
Preview
 Text. Filename: Kitaev_JGT2016_Existence_of_representation_of_graphs.pdf
Accepted Author Manuscript
Download (77kB)| Preview

Abstract

Recently, Jones et al. introduced the study of μ-representable graphs, where μ is a word over { 1,2} containing at least one 1. The notion of a μ-representable graph is a far-reaching generalization of the notion of a word-representable graph studied in the literature in a series of papers. Jones et al. have shown that any graph is 11⋯1-representable assuming that the number of 1s is at least three, while the class of 12-rerpesentable graphs is properly contained in the class of comparability graphs, which, in turn, is properly contained in the class of word-representable graphs corresponding to 11-representable graphs. Further studies in this direction were conducted by Nabawanda, who has shown, in particular, that the class of 112-representable graphs is not included in the class of word-representable graphs. Jones et al. raised a question on classification of μ-representable graphs at least for small values of μ. In this paper we show that if μ is of length at least 3 then any graph is μ-representable. This rather unexpected result shows that from existence of representation point of view there are only two interesting non-equivalent cases in the theory of μ-representable graphs, namely, those of μ=11 and μ=12.

ORCID iDs

Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647;
  • Item type:Article
    ID code:57302
    Dates:
    Date
    Event
    31 July 2017
    Published
    28 September 2016
    Published Online
    25 May 2016
    Accepted
    Notes:This is the accepted version of the following article: Kitaev, S. (2016). Existence of μ-representation of graphs. Journal of Graph Theory. which has been published in final form at http://onlinelibrary.wiley.com/journal/10.1002/(ISSN)1097-0118 . This article may be used for non-commercial purposes in accordance with the Wiley Self-Archiving Policy [http://olabout.wiley.com/WileyCDA/Section/id-828039.html].
    Keywords:μ-representable graph, pattern matching, pattern avoidance, word-representable graphs, Mathematics, Mathematics(all)
    Subjects:Science > Mathematics
    Department:Faculty of Science > Computer and Information Sciences
    Depositing user: Pure Administrator
    Date deposited:05 Aug 2016 13:42
    Last modified:30 Nov 2021 01:51
    Related URLs:
    URI:https://strathprints.strath.ac.uk/id/eprint/57302
CORE (COnnecting REpositories)