Abstract
| Original language | English |
|---|---|
| Article number | P2.53 |
| Number of pages | 20 |
| Journal | The Electronic Journal of Combinatorics |
| Volume | 22 |
| Issue number | 2 |
| Early online date | 15 Jun 2015 |
| Publication status | Published - 2015 |
Fingerprint
Keywords
- word-representable graphs
- ladder graphs
- grid graphs
- permutation graphs
- co-interval graphs
- comparability graphs
- pattern avoidance
Cite this
}
Representing graphs via pattern avoiding words. / Jones, Miles; Kitaev, Sergey; Pyatkin, Artem; Remmel, Jeffrey.
In: The Electronic Journal of Combinatorics, Vol. 22, No. 2, P2.53, 2015.Research output: Contribution to journal › Article
TY - JOUR
T1 - Representing graphs via pattern avoiding words
AU - Jones, Miles
AU - Kitaev, Sergey
AU - Pyatkin, Artem
AU - Remmel, Jeffrey
PY - 2015
Y1 - 2015
N2 - The notion of a word-representable graph has been studied in a series of papers in the literature. A 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 . If V = {1,...,n}, this is equivalent to saying that G is word-representable if for all x,y ϵ {1,…,n}, xy ϵ E if and only if the subword w {x,y} of w consisting of all occurrences of x or y in w has no consecutive occurrence of the pattern 11. In this paper, we introduce the study of u -representable graphs for any word u ϵ {1, 2}*. A graph G is u -representable if and only if there is a vertex-labeled version of G, G = ( {1,…,n},E ), and a word w ϵ {1,…,n}* such that for all x,y ϵ {1,…,n}, xy ϵ E if and only if w {x,y} has no consecutive occurrence of the pattern u . Thus, word-representable graphs are just 11-representable graphs. We show that for any k > 3, every finite graph G is 1 k - representable. This contrasts with the fact that not all graphs are 11-representable graphs. The main focus of the paper is the study of 12-representable graphs. In particular, we classify the 12-representable trees. We show that any 12-representable graph is a comparability graph and the class of 12-representable graphs include the classes of co-interval graphs and permutation graphs. We also state a number of facts on 12-representation of induced subgraphs of a grid graph.
AB - The notion of a word-representable graph has been studied in a series of papers in the literature. A 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 . If V = {1,...,n}, this is equivalent to saying that G is word-representable if for all x,y ϵ {1,…,n}, xy ϵ E if and only if the subword w {x,y} of w consisting of all occurrences of x or y in w has no consecutive occurrence of the pattern 11. In this paper, we introduce the study of u -representable graphs for any word u ϵ {1, 2}*. A graph G is u -representable if and only if there is a vertex-labeled version of G, G = ( {1,…,n},E ), and a word w ϵ {1,…,n}* such that for all x,y ϵ {1,…,n}, xy ϵ E if and only if w {x,y} has no consecutive occurrence of the pattern u . Thus, word-representable graphs are just 11-representable graphs. We show that for any k > 3, every finite graph G is 1 k - representable. This contrasts with the fact that not all graphs are 11-representable graphs. The main focus of the paper is the study of 12-representable graphs. In particular, we classify the 12-representable trees. We show that any 12-representable graph is a comparability graph and the class of 12-representable graphs include the classes of co-interval graphs and permutation graphs. We also state a number of facts on 12-representation of induced subgraphs of a grid graph.
KW - word-representable graphs
KW - ladder graphs
KW - grid graphs
KW - permutation graphs
KW - co-interval graphs
KW - comparability graphs
KW - pattern avoidance
UR - http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p53
M3 - Article
VL - 22
JO - The Electronic Journal of Combinatorics
JF - The Electronic Journal of Combinatorics
SN - 1077-8926
IS - 2
M1 - P2.53
ER -