Representing graphs via pattern avoiding words

MaRDI QIDQ491554zbMATH OpenFDO

Authors Sergey Kitaev, Miles E. Jones, Artem Pyatkin, Jeffrey Remmel

Publication date 26 August 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.4994, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p53

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

pattern avoidancepermutation graphsgrid graphscomparability graphsladder graphsco-interval graphsword-representable graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

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,ldots,n$, this is equivalent to saying that $G$ is word-representable if for all $x,yin1,ldots,n$, $xyinE$ 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 $uin{1,2}^{\ast }$. A graph $G$ is $u$-representable if and only if there is a labeled version of $G$, $G=(1,ldots,n,E)$, and a word $win{1,ldots,n}^{\ast }$ such that for all $x,yin1,ldots,n$, $xyinE$ 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 $kgeq3$, 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.

Recommendations

• On 132-representable graphs
• On graphs representable by pattern-avoiding words
• On \(k\)-\(11\)-representable graphs
• On representable graphs

Cites work

• scientific article; zbMATH DE number 1862431 (Why is no real title available?)
• A Characterization of Comparability Graphs and of Interval Graphs
• Alternation graphs
• Graphs Capturing Alternations in Words
• New results on word-representable graphs
• On graphs with representation number 3
• On representable graphs
• On the Representability of Line Graphs
• On word-representability of polyomino triangulations
• Partial orders of dimension 2
• Patterns in permutations and words.
• Word problem of the Perkins semigroup via directed acyclic graphs.
• Word-representability of line graphs
• Words and graphs

Cited in

(15)

• On 132-representable graphs
• Existence of \(u\)-representation of graphs
• On the 12-representability of induced subgraphs of a grid graph
• Representing split graphs by words
• Forbidden pattern characterizations of 12-representable graphs defined by pattern-avoiding words
• The \(k\)-dimensional cube is \(k\)-representable
• New tools to study 1-11-representation of graphs
• On representable graphs
• Word-Representable Graphs: a Survey
• Word-representable graphs from a word's perspective
• Computing shortest 12-representants of labeled graphs
• scientific article; zbMATH DE number 5999572 (Why is no real title available?)
• The combinatorics of Jeff Remmel
• On \(k\)-\(11\)-representable graphs
• On graphs representable by pattern-avoiding words

This page was built for publication: Representing graphs via pattern avoiding words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q491554)