The smallest pair of cospectral cubic graphs with different chromatic indexes

DOI10.1016/J.DAM.2021.12.016MaRDI QIDQ2065795zbMATH OpenOpenAlexFDO

Authors Zhidan Yan, Wei Wang

Publication date 13 January 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

cospectral graphscubic graphchromatic indexGM-switchingrational orthogonal matrix

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: Using an exhaustive search on cubic graphs of order 16, we find a unique cospectral pair with different chromatic indexes. This example indicates that the chromatic index of a regular graph is not characterized by its spectrum, which answers a question recently posed in [O. Etesami, W. H. Haemers, On NP-hard graph properties characterized by the spectrum, Discrete Appl. Math., 285(2020)526-529]. We prove that any orthogonal matrix representing the similarity between the two adjacency matrices of the cospectral pair cannot be rational. This implies that the cospectral pair cannot be obtained using the original GM-switching method or its generalizations based on rational orthogonal matrices.

Recommendations

• Constructing families of cospectral regular graphs
• Cospectral graphs, GM-switching and regular rational orthogonal matrices of level \(p\)
• Constructing cospectral graphs via regular rational orthogonal matrices with level two
• Enumeration of cospectral graphs.
• Cospectral regular graphs with and without a perfect matching

Cites work

• scientific article; zbMATH DE number 5125630 (Why is no real title available?)
• A note on non-\(\mathbb{R}\)-cospectral graphs
• Constructing cospectral graphs
• Cospectral graphs and regular orthogonal matrices of level 2
• Cospectral graphs, GM-switching and regular rational orthogonal matrices of level \(p\)
• Cospectral pairs of regular graphs with different connectivity
• Cospectral regular graphs with and without a perfect matching
• Distance-regularity and the spectrum of graphs
• Generalized cospectral graphs with and without Hamiltonian cycles
• Graphs cospectral with distance-regular graphs
• On NP-hard graph properties characterized by the spectrum
• On a theorem of Godsil and McKay concerning the construction of cospectral graphs
• Practical graph isomorphism. II.
• The NP-Completeness of Edge-Coloring
• The Petersen graph is not 1-factorable: postscript to `The Petersen graph is not 3-edge-colorable -- a new proof' [Discrete Math. 268 (2003) 325--326]
• The Petersen graph is not 3-edge-colorable---a new proof
• The chromatic index of strongly regular graphs

Describes a project that uses

Uses Software

• Traces
• SageMath
• nauty

This page was built for publication: The smallest pair of cospectral cubic graphs with different chromatic indexes

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