### Abstract

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 language | English |
---|---|

Pages (from-to) | 661-668 |

Number of pages | 8 |

Journal | Journal of Graph Theory |

Volume | 85 |

Issue number | 3 |

Early online date | 28 Sep 2016 |

DOIs | |

Publication status | Published - 31 Jul 2017 |

### Fingerprint

### Keywords

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

### Cite this

*Journal of Graph Theory*,

*85*(3), 661-668. https://doi.org/10.1002/jgt.22097

}

*Journal of Graph Theory*, vol. 85, no. 3, pp. 661-668. https://doi.org/10.1002/jgt.22097

**Existence of μ-representation of graphs.** / Kitaev, Sergey.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Existence of μ-representation of graphs

AU - Kitaev, Sergey

N1 - 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].

PY - 2017/7/31

Y1 - 2017/7/31

N2 - 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.

AB - 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.

KW - μ-representable graph

KW - pattern matching

KW - pattern avoidance

KW - word-representable graphs

UR - http://onlinelibrary.wiley.com/journal/10.1002/(ISSN)1097-0118

U2 - 10.1002/jgt.22097

DO - 10.1002/jgt.22097

M3 - Article

VL - 85

SP - 661

EP - 668

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 3

ER -