Journal of Combinatorics

Volume 10 (2019)

Number 3

Special Issue in Memory of Jeff Remmel, Part 1 of 2

Guest Editor: Nicholas A. Loehr

On $k\textrm{-}11$-representable graphs

Pages: 491 – 513

DOI: https://dx.doi.org/10.4310/JOC.2019.v10.n3.a3

Authors

Gi-Sang Cheon (Applied Algebra and Optimization Research Center, Department of Mathematics, Sungkyunkwan University, Suwon, South Korea)

Jinha Kim (Department of Mathematical Sciences, Seoul National University, Seoul, South Korea)

Minki Kim (Department of Mathematics, Technion – Israel Institute of Technology, Haifa, Israel)

Sergey Kitaev (Department of Computer and Information Sciences, University of Strathclyde, Glasgow, Scotland, United Kingdom)

Artem Pyatkin (Sobolev Institute of Mathematics, Novosibirsk State University, Novosibirsk, Russia)

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\textrm{-}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\textrm{-}11$-representable graphs. Our key result in this paper is showing that every graph is $2\textrm{-}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\textrm{-}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\textrm{-}11$-representable graphs. Another result that we prove is the fact that the class of interval graphs is precisely the class of $1\textrm{-}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\textrm{-}11$-representable graphs that can be represented by uniform words containing two copies of each letter.

Keywords

On $k\textrm{-}11$-representable graph, word-representable graph

2010 Mathematics Subject Classification

05C62, 68R15

Received 3 March 2018

Published 23 May 2019