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$. The proof is based on the theory of coherent configurations.

arXiv comment10 pages, 4 figures