New Tools to Study 1-11-Representation of Graphs | Sciact - Система учета научной деятельности ИМ СО РАН

New Tools to Study 1-11-Representation of Graphs Научная публикация

Журнал

Graphs and Combinatorics
ISSN: 0911-0119 , E-ISSN: 1435-5914

Вых. Данные

Год: 2024, Том: 40, Номер: 5, Страницы: 1-13 Страниц : 13 DOI: 10.1007/s00373-024-02825-1

Ключевые слова

1-11-representable graph · Word-representable graph · Chvátal graph · Split graph · Mycielski graph · Comparability graph

Авторы

Kitaev Sergey ¹ , Futorny Mikhail ² , Pyatkin Artem ³

Организации

1	Institute of Mathematics and Statistics, University of São Paulo, R.do Matão, São Paulo 1010, Brazil
2	Department of Mathematics and Statistics, University of Strathclyde, 26 Richmond Street, Glasgow G1 1XH, UK
3	Sobolev Institute of Mathematics, Koptyug ave, 4, Novosibirsk 630090, Russia

Информация о финансировании (1)

Институт математики им. С.Л. Соболева СО РАН

FWNF-2022-0019

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. Agraph G isk-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 Cheonatal. is that 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 111-representation of Chvátal graph, Mycielski graph, split graphs, and graphs whose vertices can be partitioned into a comparability graph and an independent set.

Kitaev S. , Futorny M. , Pyatkin A.
New Tools to Study 1-11-Representation of Graphs
Graphs and Combinatorics. 2024. V.40. N5. P.1-13. DOI: 10.1007/s00373-024-02825-1 WOS Scopus РИНЦ OpenAlex

Поступила в редакцию:	24 мар. 2024 г.
Принята к публикации:	26 июл. 2024 г.
Опубликована в печати:	14 авг. 2024 г.
Опубликована online:	14 авг. 2024 г.

Web of science:	WOS:001290250900001
Scopus:	2-s2.0-85201262223
РИНЦ:	73624013
OpenAlex:	W4401556672

БД	Цитирований
Scopus	1