The Weisfeiler–Leman Dimension of Chordal Bipartite Graphs Without Bipartite Claw Научная публикация
| Журнал |
Graphs and Combinatorics
ISSN: 0911-0119 , E-ISSN: 1435-5914 |
||||||
|---|---|---|---|---|---|---|---|
| Вых. Данные | Год: 2021, Том: 37, Номер: 3, Страницы: 1089-1102 Страниц : 14 DOI: 10.1007/s00373-021-02308-7 | ||||||
| Ключевые слова | Graph isomorphism problem, Weisfeiler–Leman dimension, Coherent configuration | ||||||
| Авторы |
|
||||||
| Организации |
|
Реферат:
A graph X is said to be chordal bipartite if it is bipartite and contains no induced cycle of length at least 6. It is proved that if X does not contain bipartite claw as an induced subgraph, then the Weisfeiler–Leman dimension of X is at most 3. This
implies that the Weisfeiler–Leman dimension of any bipartite permutation graph is at most 3. The proof is based on the theory of coherent configurations.
Библиографическая ссылка:
Ponomarenko I.
, Ryabov G.
The Weisfeiler–Leman Dimension of Chordal Bipartite Graphs Without Bipartite Claw
Graphs and Combinatorics. 2021. V.37. N3. P.1089-1102. DOI: 10.1007/s00373-021-02308-7 WOS Scopus OpenAlex
The Weisfeiler–Leman Dimension of Chordal Bipartite Graphs Without Bipartite Claw
Graphs and Combinatorics. 2021. V.37. N3. P.1089-1102. DOI: 10.1007/s00373-021-02308-7 WOS Scopus OpenAlex
Даты:
| Поступила в редакцию: | 7 июл. 2020 г. |
| Принята к публикации: | 9 мар. 2021 г. |
| Опубликована в печати: | 19 мар. 2021 г. |
Идентификаторы БД:
| Web of science: | WOS:000632735800001 |
| Scopus: | 2-s2.0-85103189262 |
| OpenAlex: | W3150973893 |