On the hyperbolicity of bipartite graphs and intersection graphs

DOI10.1016/j.dam.2016.06.017zbMath1346.05243OpenAlexW2184519647MaRDI QIDQ317426

David Coudert, Guillaume Ducoffe

Publication date: 30 September 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2016.06.017

zbMATH Keywords

bipartite graphintersection graphline graphclique graphGromov hyperbolicitybiclique graphgraph power

Mathematics Subject Classification ID

Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Related Items

The hyperbolicity constant of infinite circulant graphs, Recent Results on Hyperbolicity on Unitary Operators on Graphs, On a classical theorem on the diameter and minimum degree of a graph, Strong SDP based bounds on the cutwidth of a graph, Several extremal problems on graphs involving the circumference, girth, and hyperbolicity constant, On the hyperbolicity constant of circular-arc graphs, A simple approach for lower-bounding the distortion in any hyperbolic embedding, Unnamed Item, Gromov hyperbolicity in the Cartesian sum of graphs, Gromov hyperbolicity in Mycielskian graphs, Hyperbolicity on graph operators, Biclique graphs of split graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Data center interconnection networks are not hyperbolic
• Hyperbolicity and chordality of a graph
• On the hyperbolicity constant of line graphs
• Distance-hereditary graphs
• Edge-clique graphs
• On metric properties of certain clique graphs
• Old and new generalizations of line graphs
• Powers of distance-hereditary graphs
• On Computing the Gromov Hyperbolicity
• Recognition of $C_4$-Free and 1/2-Hyperbolic Graphs
• On Computing the Hyperbolicity of Real-World Graphs
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• A common generalization of line graphs and clique graphs
• 1-Hyperbolic Graphs
• Biclique graphs and biclique matrices
• Fast computation of empirically tight bounds for the diameter of massive graphs
• Total Graphs and Traversability
• A partial characterization of clique graphs
• To Approximate Treewidth, Use Treelength!