Representing graphs via pattern avoiding words

Miles Jones, Sergey Kitaev, Artem Pyatkin, Jeffrey Remmel

Research output: Contribution to journalArticle

4 Citations (Scopus)
52 Downloads (Pure)

Abstract

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.
Original languageEnglish
Article numberP2.53
Number of pages20
JournalThe Electronic Journal of Combinatorics
Volume22
Issue number2
Early online date15 Jun 2015
Publication statusPublished - 2015

Fingerprint

Graph in graph theory
If and only if
Consecutive
Comparability Graph
Permutation Graphs
Grid Graph
Subword
Interval Graphs
Finite Graph
Induced Subgraph
Alternate
Classify
Series
Vertex of a graph
Class

Keywords

  • word-representable graphs
  • ladder graphs
  • grid graphs
  • permutation graphs
  • co-interval graphs
  • comparability graphs
  • pattern avoidance

Cite this

Jones, M., Kitaev, S., Pyatkin, A., & Remmel, J. (2015). Representing graphs via pattern avoiding words. The Electronic Journal of Combinatorics, 22(2), [P2.53].
Jones, Miles ; Kitaev, Sergey ; Pyatkin, Artem ; Remmel, Jeffrey. / Representing graphs via pattern avoiding words. In: The Electronic Journal of Combinatorics. 2015 ; Vol. 22, No. 2.
@article{5111092bd1aa4d5984b28e1f9dd47bc1,
title = "Representing graphs via pattern avoiding words",
abstract = "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.",
keywords = "word-representable graphs, ladder graphs, grid graphs, permutation graphs, co-interval graphs, comparability graphs, pattern avoidance",
author = "Miles Jones and Sergey Kitaev and Artem Pyatkin and Jeffrey Remmel",
year = "2015",
language = "English",
volume = "22",
journal = "The Electronic Journal of Combinatorics",
issn = "1077-8926",
number = "2",

}

Jones, M, Kitaev, S, Pyatkin, A & Remmel, J 2015, 'Representing graphs via pattern avoiding words', The Electronic Journal of Combinatorics, vol. 22, no. 2, P2.53.

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 journalArticle

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 -