Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
The Weisfeiler–Leman Dimension of Chordal Bipartite Graphs Without Bipartite Claw. / Ponomarenko, Ilia; Ryabov, Grigory.
в: Graphs and Combinatorics, Том 37, № 3, 05.2021, стр. 1089-1102.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - The Weisfeiler–Leman Dimension of Chordal Bipartite Graphs Without Bipartite Claw
AU - Ponomarenko, Ilia
AU - Ryabov, Grigory
N1 - Publisher Copyright: © 2021, The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.
PY - 2021/5
Y1 - 2021/5
N2 - 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.
AB - 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.
KW - Coherent configuration
KW - Graph isomorphism problem
KW - Weisfeiler–Leman dimension
UR - http://www.scopus.com/inward/record.url?scp=85103189262&partnerID=8YFLogxK
U2 - 10.1007/s00373-021-02308-7
DO - 10.1007/s00373-021-02308-7
M3 - Article
AN - SCOPUS:85103189262
VL - 37
SP - 1089
EP - 1102
JO - Graphs and Combinatorics
JF - Graphs and Combinatorics
SN - 0911-0119
IS - 3
ER -
ID: 28212259