Graph Coloring Using Eigenvalue Decomposition

DOI10.1137/0605051MaRDI QIDQ3216692zbMATH OpenOpenAlexFDO

Authors Bengt Aspvall, J. R. Gilbert

Publication date 1984

Published in SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL https://hdl.handle.net/1813/6385

zbMATH Keywords

eigenvectors of the adjacency matrixvertex colouring

Mathematics Subject Classification ID

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

Recommendations

• Some sequential graph colouring algorithms
• Local optimization of colorings of graphs
• scientific article; zbMATH DE number 4210190
• scientific article; zbMATH DE number 1189239
• scientific article; zbMATH DE number 4187836

Cites work

• An Algorithm for Partitioning the Nodes of a Graph
• An upper bound for the chromatic number of a graph and its application to timetabling problems
• Error Bounds for Approximate Invariant Subspaces of Closed Linear Operators
• Estimation of Sparse Jacobian Matrices and Graph Coloring Blems
• scientific article; zbMATH DE number 3671573 (Why is no real title available?)
• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• scientific article; zbMATH DE number 3473182 (Why is no real title available?)
• scientific article; zbMATH DE number 3553637 (Why is no real title available?)
• scientific article; zbMATH DE number 3215568 (Why is no real title available?)
• scientific article; zbMATH DE number 3349875 (Why is no real title available?)
• scientific article; zbMATH DE number 3383914 (Why is no real title available?)
• scientific article; zbMATH DE number 3394189 (Why is no real title available?)
• scientific article; zbMATH DE number 3404264 (Why is no real title available?)
• scientific article; zbMATH DE number 3420184 (Why is no real title available?)
• Identification of algebraic numbers
• Linear Algebra in Geography: Eigenvectors of Networks
• New methods to color the vertices of a graph
• On coloring graphs to maximize the proportion of multicolored k-edges
• Singular Value Analysis of Cryptograms
• The Complexity of Near-Optimal Graph Coloring
• The Eigenvalues of a Graph and Its Chromatic Number
• The Rotation of Eigenvectors by a Perturbation. III

Cited in

(11)

• Graph partitioning by eigenvectors
• Hardness results and spectral techniques for combinatorial problems on circulant graphs
• Heuristic methods and applications: A categorized survey
• Graph Laplacians, nodal domains, and hyperplane arrangements
• Graph coarsening: from scientific computing to machine learning
• Eigen-stratified models
• Cheeger inequalities for general edge-weighted directed graphs
• scientific article; zbMATH DE number 4091188 (Why is no real title available?)
• Minimum supports of eigenfunctions of graphs: a survey
• Metric uniformization and spectral bounds for graphs
• Software for proper vertex-colouring exploiting graph symmetry

This page was built for publication: Graph Coloring Using Eigenvalue Decomposition

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