The Weisfeiler-Leman dimension of chordal bipartite graphs without bipartite claw

DOI10.1007/S00373-021-02308-7MaRDI QIDQ2045400zbMATH OpenOpenAlexFDO

Authors Ilya Ponomarenko, Grigoriĭ Konstantinovich Ryabov

Publication date 12 August 2021

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.01678

zbMATH Keywords

coherent configurationgraph isomorphism problemWeisfeiler-Leman dimension

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85)

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.

Recommendations

• The Weisfeiler-Leman dimension of planar graphs is at most 3
• The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
• Chordal bipartite graphs of bounded tree- and clique-width
• scientific article; zbMATH DE number 512817
• On Weisfeiler-Leman invariance: subgraph counts and related graph properties

Cites work

• Algorithmic graph theory and perfect graphs
• An optimal lower bound on the number of variables for graph identification
• Clique-width for hereditary graph classes
• Coherent configurations associated with TI-subgroups
• Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
• Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
• Graph isomorphism in quasipolynomial time (extended abstract)
• Graph isomorphism, color refinement, and compactness
• Graphs identified by logics with counting
• scientific article; zbMATH DE number 7561610 (Why is no real title available?)
• Interval graphs: canonical representations in logspace
• On testing isomorphism of permutation graphs
• On the Weisfeiler-Leman dimension of fractional packing
• Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
• The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3

Cited in

(3)

• Graph parameters, implicit representations and factorial properties
• On the Weisfeiler-Leman dimension of permutation graphs
• On WL-rank and WL-dimension of some Deza dihedrants

This page was built for publication: The Weisfeiler-Leman dimension of chordal bipartite graphs without bipartite claw

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2045400)