Existence of μ-representation of graphs

Research output: Contribution to journalArticle

3 Citations (Scopus)
22 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)661-668
Number of pages8
JournalJournal of Graph Theory
Volume85
Issue number3
Early online date28 Sep 2016
DOIs
Publication statusPublished - 31 Jul 2017

Keywords

  • μ-representable graph
  • pattern matching
  • pattern avoidance
  • word-representable graphs

Cite this