On k-11-representable graphs

Gi-Sang Cheon, Jinha Kim, Minki Kim, Sergey Kitaev, Artem Pyatkin

Research output: Contribution to journalArticle

Abstract

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.
LanguageEnglish
Pages1-19
Number of pages19
JournalJournal of Combinatorics
Publication statusAccepted/In press - 23 Sep 2018

Keywords

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

Cite this

Cheon, G-S., Kim, J., Kim, M., Kitaev, S., & Pyatkin, A. (Accepted/In press). On k-11-representable graphs. Journal of Combinatorics, 1-19.
Cheon, Gi-Sang ; Kim, Jinha ; Kim, Minki ; Kitaev, Sergey ; Pyatkin, Artem. / On k-11-representable graphs. In: Journal of Combinatorics. 2018 ; pp. 1-19.
@article{af398b0438dd4f1092c5cfec1a66d252,
title = "On k-11-representable graphs",
abstract = "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.",
keywords = "k-11-representable graph, word-representable graph",
author = "Gi-Sang Cheon and Jinha Kim and Minki Kim and Sergey Kitaev and Artem Pyatkin",
year = "2018",
month = "9",
day = "23",
language = "English",
pages = "1--19",
journal = "Journal of Combinatorics",
issn = "2156-3527",

}

Cheon, G-S, Kim, J, Kim, M, Kitaev, S & Pyatkin, A 2018, 'On 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.

In: Journal of Combinatorics, 23.09.2018, p. 1-19.

Research output: Contribution to journalArticle

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

T2 - Journal of Combinatorics

JF - Journal of Combinatorics

SN - 2156-3527

ER -

Cheon G-S, Kim J, Kim M, Kitaev S, Pyatkin A. On k-11-representable graphs. Journal of Combinatorics. 2018 Sep 23;1-19.