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

Ilia Ponomarenko, Grigory Ryabov

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish
JournalGraphs and Combinatorics
DOIs
Publication statusPublished - Mar 2021

Keywords

  • Coherent configuration
  • Graph isomorphism problem
  • Weisfeiler–Leman dimension

OECD FOS+WOS

  • 1.02 COMPUTER AND INFORMATION SCIENCES
  • 1.01 MATHEMATICS

Fingerprint

Dive into the research topics of 'The Weisfeiler–Leman Dimension of Chordal Bipartite Graphs Without Bipartite Claw'. Together they form a unique fingerprint.

Cite this