On the power of combinatorial and spectral invariants

DOI10.1016/j.laa.2009.07.019zbMath1217.05141OpenAlexW1970491586MaRDI QIDQ962126

Martin Fuerer

Publication date: 6 April 2010

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.laa.2009.07.019

zbMATH Keywords

edge coloringspectral propertiesstarlike trees2-dim W-L

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15)

Related Items (5)

On the Combinatorial Power of the Weisfeiler-Lehman Algorithm ⋮ On the Weisfeiler-Leman dimension of fractional packing ⋮ Unnamed Item ⋮ On the expressive power of linear algebra on graphs ⋮ On Weisfeiler-Leman invariance: subgraph counts and related graph properties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Constructing trees with given eigenvalues and angles
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• An optimal lower bound on the number of variables for graph identification
• On construction and identification of graphs. With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler
• Random Graph Isomorphism
• The graph isomorphism disease
• Some trees characterized by eigenvalues and angles
• No starlike trees are cospectral

This page was built for publication: On the power of combinatorial and spectral invariants