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.
- Coherent configuration
- Graph isomorphism problem
- Weisfeiler–Leman dimension
- 1.02 COMPUTER AND INFORMATION SCIENCES
- 1.01 MATHEMATICS