The Weisfeiler–Leman Dimension of Chordal Bipartite Graphs Without Bipartite Claw Full article
| Journal |
Graphs and Combinatorics
ISSN: 0911-0119 , E-ISSN: 1435-5914 |
||||||
|---|---|---|---|---|---|---|---|
| Output data | Year: 2021, Volume: 37, Number: 3, Pages: 1089-1102 Pages count : 14 DOI: 10.1007/s00373-021-02308-7 | ||||||
| Tags | Graph isomorphism problem, Weisfeiler–Leman dimension, Coherent configuration | ||||||
| Authors |
|
||||||
| Affiliations |
|
Abstract:
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.
Cite:
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
Dates:
| Submitted: | Jul 7, 2020 |
| Accepted: | Mar 9, 2021 |
| Published print: | Mar 19, 2021 |
Identifiers:
| Web of science: | WOS:000632735800001 |
| Scopus: | 2-s2.0-85103189262 |
| OpenAlex: | W3150973893 |