### Abstract

Thus, edges of G are defined by avoiding the consecutive pattern 11 in a word representing G, that is, by avoiding xx and yy.

In 2017, Jeff Remmel introduced the notion of a k-11-representable graph for a non-negative integer k, which generalizes the notion of a word-representable graph. Under this representation, edges of G are defined by containing at most k occurrences of the consecutive pattern 11 in a word representing G. Thus, word-representable graphs are precisely 0-11-representable graphs. Our key result in this paper is showing that every graph is 2-11-representable by a concatenation of permutations, which is rather surprising taking into account that concatenation of permutations has limited power in the case of 0-11-representation. Also, we show that the class of word-representable graphs, studied intensively in the literature, is contained strictly in the class of 1-11-representable graphs. Another result that we prove is the fact that the class of interval graphs is precisely the class of 1-11-representable graphs that can be represented by uniform words containing two copies of each letter. This result can be compared with the known fact that the class of circle graphs is precisely the class of 0-11-representable graphs that can be represented by uniform words containing two copies of each letter.

Original language | English |
---|---|

Pages (from-to) | 1-19 |

Number of pages | 19 |

Journal | Journal of Combinatorics |

Publication status | Accepted/In press - 23 Sep 2018 |

### Keywords

- k-11-representable graph
- word-representable graph

### Cite this

*k*-11-representable graphs.

*Journal of Combinatorics*, 1-19.

}

*k*-11-representable graphs',

*Journal of Combinatorics*, pp. 1-19.

**On k-11-representable graphs.** / Cheon, Gi-Sang; Kim, Jinha; Kim, Minki; Kitaev, Sergey; Pyatkin, Artem.

Research output: Contribution to journal › Article

TY - JOUR

T1 - On k-11-representable graphs

AU - Cheon, Gi-Sang

AU - Kim, Jinha

AU - Kim, Minki

AU - Kitaev, Sergey

AU - Pyatkin, Artem

PY - 2018/9/23

Y1 - 2018/9/23

N2 - Distinct letters x and y alternate in a word w if after deleting in w all letters but the copies of x and y we either obtain a word of the form xyxy... (of even or odd length) or a word of the form yxyx... (of even or odd length). A simple graph G=(V,E) is word-representable if there exists a word w over the alphabet V such that letters x and y alternate in w if and only if xy is an edge in E. Thus, edges of G are defined by avoiding the consecutive pattern 11 in a word representing G, that is, by avoiding xx and yy. In 2017, Jeff Remmel introduced the notion of a k-11-representable graph for a non-negative integer k, which generalizes the notion of a word-representable graph. Under this representation, edges of G are defined by containing at most k occurrences of the consecutive pattern 11 in a word representing G. Thus, word-representable graphs are precisely 0-11-representable graphs. Our key result in this paper is showing that every graph is 2-11-representable by a concatenation of permutations, which is rather surprising taking into account that concatenation of permutations has limited power in the case of 0-11-representation. Also, we show that the class of word-representable graphs, studied intensively in the literature, is contained strictly in the class of 1-11-representable graphs. Another result that we prove is the fact that the class of interval graphs is precisely the class of 1-11-representable graphs that can be represented by uniform words containing two copies of each letter. This result can be compared with the known fact that the class of circle graphs is precisely the class of 0-11-representable graphs that can be represented by uniform words containing two copies of each letter.

AB - Distinct letters x and y alternate in a word w if after deleting in w all letters but the copies of x and y we either obtain a word of the form xyxy... (of even or odd length) or a word of the form yxyx... (of even or odd length). A simple graph G=(V,E) is word-representable if there exists a word w over the alphabet V such that letters x and y alternate in w if and only if xy is an edge in E. Thus, edges of G are defined by avoiding the consecutive pattern 11 in a word representing G, that is, by avoiding xx and yy. In 2017, Jeff Remmel introduced the notion of a k-11-representable graph for a non-negative integer k, which generalizes the notion of a word-representable graph. Under this representation, edges of G are defined by containing at most k occurrences of the consecutive pattern 11 in a word representing G. Thus, word-representable graphs are precisely 0-11-representable graphs. Our key result in this paper is showing that every graph is 2-11-representable by a concatenation of permutations, which is rather surprising taking into account that concatenation of permutations has limited power in the case of 0-11-representation. Also, we show that the class of word-representable graphs, studied intensively in the literature, is contained strictly in the class of 1-11-representable graphs. Another result that we prove is the fact that the class of interval graphs is precisely the class of 1-11-representable graphs that can be represented by uniform words containing two copies of each letter. This result can be compared with the known fact that the class of circle graphs is precisely the class of 0-11-representable graphs that can be represented by uniform words containing two copies of each letter.

KW - k-11-representable graph

KW - word-representable graph

UR - http://intlpress.com/site/pub/pages/journals/items/joc/_home/_main/

M3 - Article

SP - 1

EP - 19

JO - Journal of Combinatorics

JF - Journal of Combinatorics

SN - 2156-3527

ER -

*k*-11-representable graphs. Journal of Combinatorics. 2018 Sep 23;1-19.