The Weisfeiler–Leman Dimension of Chordal Bipartite Graphs Without Bipartite Claw

Standard

The Weisfeiler–Leman Dimension of Chordal Bipartite Graphs Without Bipartite Claw. / Ponomarenko, Ilia; Ryabov, Grigory.

In: Graphs and Combinatorics, Vol. 37, No. 3, 05.2021, p. 1089-1102.

Research output: Contribution to journal › Article › peer-review

Harvard

Ponomarenko, I & Ryabov, G 2021, 'The Weisfeiler–Leman Dimension of Chordal Bipartite Graphs Without Bipartite Claw', Graphs and Combinatorics, vol. 37, no. 3, pp. 1089-1102. https://doi.org/10.1007/s00373-021-02308-7

APA

Ponomarenko, I., & Ryabov, G. (2021). The Weisfeiler–Leman Dimension of Chordal Bipartite Graphs Without Bipartite Claw. Graphs and Combinatorics, 37(3), 1089-1102. https://doi.org/10.1007/s00373-021-02308-7

Vancouver

Ponomarenko I, Ryabov G. The Weisfeiler–Leman Dimension of Chordal Bipartite Graphs Without Bipartite Claw. Graphs and Combinatorics. 2021 May;37(3):1089-1102. doi: 10.1007/s00373-021-02308-7

Author

Ponomarenko, Ilia ; Ryabov, Grigory. / The Weisfeiler–Leman Dimension of Chordal Bipartite Graphs Without Bipartite Claw. In: Graphs and Combinatorics. 2021 ; Vol. 37, No. 3. pp. 1089-1102.

BibTeX

@article{e264b222759f4d01bb98e6807b8921a4,

title = "The Weisfeiler–Leman Dimension of Chordal Bipartite Graphs Without Bipartite Claw",

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.",

keywords = "Coherent configuration, Graph isomorphism problem, Weisfeiler–Leman dimension",

author = "Ilia Ponomarenko and Grigory Ryabov",

note = "Publisher Copyright: {\textcopyright} 2021, The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.",

year = "2021",

month = may,

doi = "10.1007/s00373-021-02308-7",

language = "English",

volume = "37",

pages = "1089--1102",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "3",

}

RIS

TY - JOUR

T1 - The Weisfeiler–Leman Dimension of Chordal Bipartite Graphs Without Bipartite Claw

AU - Ponomarenko, Ilia

AU - Ryabov, Grigory

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