The smallest pair of cospectral cubic graphs with different chromatic indexes

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.

• Publication year

  2021

• Venue

  Discrete Applied Mathematics

• Publication date

  2021-12-12

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.dam.2021.12.016arXiv 2112.06112
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On a theorem of Godsil and McKay concerning the construction of cospectral graphs

  2020cited by this paper
• Generalized cospectral graphs with and without Hamiltonian cycles

  2020cited by this paper
• Cospectral Pairs of Regular Graphs with Different Connectivity

  2019cited by this paper
• On NP-hard graph properties characterized by the spectrum

  2019influential reference
• Cospectral graphs, GM-switching and regular rational orthogonal matrices of level p

  2019cited by this paper
• The chromatic index of strongly regular graphs

  2018cited by this paper
• A Note on Non-ℝ-Cospectral Graphs

  2017cited by this paper
• A note on non-R-cospectral graphs

  2017cited by this paper
• Cospectral regular graphs with and without a perfect matching

  2014cited by this paper
• Practical graph isomorphism, II

  2013cited by this paper
• Cospectral Graphs and Regular Orthogonal Matrices of Level 2

  2012cited by this paper
• Cospectral graphs

  2011cited by this paper
• Connected co-spectral graphs are not necessarily both Hamiltonian

  2005cited by this paper
• 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]

  2004cited by this paper
• The Petersen graph is not 3-edge-colorable--a new proof

  2003cited by this paper
• Distance regularity and the spectrum of graphs

  1996cited by this paper
• Graphs cospectral with distance-regular graphs

  1995cited by this paper
• Constructing cospectral graphs

  1982cited by this paper
• The NP-Completeness of Edge-Coloring

  1981cited by this paper

• On perfect matchings, edge-colourings and eigenvalues of cubic graphs

  2026cites this paper
• Counting cospectral graphs obtained via switching

  2025cites this paper