Graph Coloring Using Eigenvalue Decomposition
From MaRDI portal
Publication:3216692
DOI10.1137/0605051zbMath0554.05048OpenAlexW1965419829MaRDI QIDQ3216692
John R. Gilbert, Bengt Aspvall
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
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15)
Related Items
Minimum supports of eigenfunctions of graphs: a survey, Graph coarsening: from scientific computing to machine learning, Graph Laplacians, nodal domains, and hyperplane arrangements, Eigen-stratified models, Cheeger Inequalities for General Edge-Weighted Directed Graphs, Graph partitioning by eigenvectors, Hardness results and spectral techniques for combinatorial problems on circulant graphs, Metric uniformization and spectral bounds for graphs, Multi-way spectral partitioning and higher-order cheeger inequalities, Diffusion representations, Heuristic methods and applications: A categorized survey
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Estimation of Sparse Jacobian Matrices and Graph Coloring Blems
- Linear Algebra in Geography: Eigenvectors of Networks
- Identification of algebraic numbers
- The Complexity of Near-Optimal Graph Coloring
- New methods to color the vertices of a graph
- An Algorithm for Partitioning the Nodes of a Graph
- Singular Value Analysis of Cryptograms
- The Eigenvalues of a Graph and Its Chromatic Number
- An upper bound for the chromatic number of a graph and its application to timetabling problems
- On coloring graphs to maximize the proportion of multicolored k-edges
- The Rotation of Eigenvectors by a Perturbation. III
- Error Bounds for Approximate Invariant Subspaces of Closed Linear Operators
