Constructing uniquely realizable graphs

DOI10.1007/S00454-013-9545-6MaRDI QIDQ393739zbMATH OpenOpenAlexFDO

Authors Igor Pak, Dan Vilenchik

Publication date 24 January 2014

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00454-013-9545-6

zbMATH Keywords

rigiditysemi-definite programminggraph colorabilitygraph realization problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Conditions for Unique Graph Realizations
• Connected rigidity matroids and unique realizations of graphs
• On rigidity and realizability of weighted graphs
• Forcing structures and cliques in uniquely vertex colorable graphs
• Realizability of graphs

Cites work

• scientific article; zbMATH DE number 1229396 (Why is no real title available?)
• scientific article; zbMATH DE number 480232 (Why is no real title available?)
• scientific article; zbMATH DE number 1182578 (Why is no real title available?)
• scientific article; zbMATH DE number 1550912 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 2188749 (Why is no real title available?)
• .878-approximation algorithms for MAX CUT and MAX 2SAT
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Approximate graph coloring by semidefinite programming
• Characterizing the universal rigidity of generic frameworks
• Circular chromatic number: A survey
• Colouring Semirandom Graphs
• Conditions for Unique Graph Realizations
• Eigenvalue bounds for independent sets
• Expander graphs and their applications
• Geometric algorithms and combinatorial optimization
• Graph partitioning via adaptive spectral techniques
• Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers
• Initialization in semidefinite programming via a self-dual skew-symmetric embedding
• On chromatic number of finite set-systems
• Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
• Problems of distance geometry and convex properties of quadratic maps
• Ramanujan graphs
• Rigidity and energy
• Rigidity and polynomial invariants of convex polytopes
• Second-Order Rigidity and Prestress Stability for Tensegrity Frameworks
• Tensegrity Frameworks
• Uniquely colorable graphs
• WHICH POINT CONFIGURATIONS ARE DETERMINED BY THE DISTRIBUTION OF THEIR PAIRWISE DISTANCES?
• Why almost all \(k\)-colorable graphs are easy to color

Cited in

(6)

• Graph homomorphisms via vector colorings
• Realizability and uniqueness in graphs
• Iterative universal rigidity
• Vector coloring the categorical product of graphs
• On (1, 2)-realizable graphs
• Universal completability, least eigenvalue frameworks, and vector colorings

This page was built for publication: Constructing uniquely realizable graphs

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