New tools to study 1-11-representation of graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914886543474688 |
|---|---|
| author | Futorny, Mikhail Kitaev, Sergey Pyatkin, Artem |
| author_facet | Futorny, Mikhail Kitaev, Sergey Pyatkin, Artem |
| contents | The notion of a $k$-11-representable graph was introduced by Jeff Remmel in 2017 and studied by Cheon et al.\ in 2019 as a natural extension of the extensively studied notion of word-representable graphs, which are precisely 0-11-representable graphs. A graph $G$ is $k$-11-representable if it can be represented by a word $w$ such that for any edge (resp., non-edge) $xy$ in $G$ the subsequence of $w$ formed by $x$ and $y$ contains at most $k$ (resp., at least $k+1$) pairs of consecutive equal letters. A remarkable result of Cheon at al.\ is that {\em any} graph is 2-11-representable, while it is unknown whether every graph is 1-11-representable. Cheon et al.\ showed that the class of 1-11-representable graphs is strictly larger than that of word-representable graphs, and they introduced a useful toolbox to study 1-11-representable graphs.
In this paper, we introduce new tools for studying 1-11-representation of graphs. We apply them for establishing 1-11-representation of Chvátal graph, Mycielski graph, split graphs, and graphs whose vertices can be partitioned into a comparability graph and an independent set. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_17784 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | New tools to study 1-11-representation of graphs Futorny, Mikhail Kitaev, Sergey Pyatkin, Artem Combinatorics The notion of a $k$-11-representable graph was introduced by Jeff Remmel in 2017 and studied by Cheon et al.\ in 2019 as a natural extension of the extensively studied notion of word-representable graphs, which are precisely 0-11-representable graphs. A graph $G$ is $k$-11-representable if it can be represented by a word $w$ such that for any edge (resp., non-edge) $xy$ in $G$ the subsequence of $w$ formed by $x$ and $y$ contains at most $k$ (resp., at least $k+1$) pairs of consecutive equal letters. A remarkable result of Cheon at al.\ is that {\em any} graph is 2-11-representable, while it is unknown whether every graph is 1-11-representable. Cheon et al.\ showed that the class of 1-11-representable graphs is strictly larger than that of word-representable graphs, and they introduced a useful toolbox to study 1-11-representable graphs. In this paper, we introduce new tools for studying 1-11-representation of graphs. We apply them for establishing 1-11-representation of Chvátal graph, Mycielski graph, split graphs, and graphs whose vertices can be partitioned into a comparability graph and an independent set. |
| title | New tools to study 1-11-representation of graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2407.17784 |