Graphs with Large Girth Not Embeddable in the Sphere

DOI10.1017/S0963548307008528zbMath1126.05042OpenAlexW2018932343MaRDI QIDQ5428364

Pierre Charbit, Steéphan Thomassé

Publication date: 22 November 2007

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548307008528

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites Work

• On combinatorial properties of spheres in euclidean spaces
• A triangle free graph which cannot be \(\sqrt3\) imbedded in any Euclidean unit sphere
• Triangle free graphs that are not \(\sqrt{3}\)-embeddable in \(S^ n\).
• Approximate graph coloring by semidefinite programming
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

This page was built for publication: Graphs with Large Girth Not Embeddable in the Sphere