Boxicity of graphs with bounded degree

DOI10.1016/J.EJC.2008.10.003MaRDI QIDQ1024326zbMATH OpenOpenAlexFDO

Authors L. Esperet

Publication date 17 June 2009

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejc.2008.10.003

zbMATH Keywords

maximum degree

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Recommendations

• Boxicity and maximum degree
• Local boxicity
• Geometric Representation of Graphs in Low Dimension
• Boxicity of line graphs
• Local boxicity and maximum degree

Cites work

• A special planar satisfiability problem and a consequence of its NP- completeness
• Boxicity and maximum degree
• Boxicity and treewidth
• Computing the boxicity of a graph by covering its complement by cointerval graphs
• scientific article; zbMATH DE number 3737705 (Why is no real title available?)
• scientific article; zbMATH DE number 3566474 (Why is no real title available?)
• scientific article; zbMATH DE number 3307331 (Why is no real title available?)
• Interval representations of planar graphs
• On the chordality of a graph

Cited in

(26)

• Local boxicity
• Intersection dimension and graph invariants
• Characterization of the graphs with boxicity \(\leq 2\)
• Lower bounds for boxicity
• A characterization of box-bounded degree sequences of graphs
• Chronological rectangle digraphs which are two-terminal series-parallel
• Boxicity and maximum degree
• Cubicity, degeneracy, and crossing number
• Local boxicity and maximum degree
• On the boxicity of Kneser graphs and complements of line graphs
• Intersection dimension and maximum degree
• Boxicity of line graphs
• scientific article; zbMATH DE number 1835115 (Why is no real title available?)
• Better bounds for poset dimension and boxicity
• Extremal Results on Intersection Graphs of Boxes in $${\mathbb R}^d$$ R d
• scientific article; zbMATH DE number 5214885 (Why is no real title available?)
• Functionality of box intersection graphs
• Vertex cover problem parameterized above and below tight bounds
• A note on lower bounds for boxicity of graphs
• Boxicity of circular arc graphs
• Boxicity and cubicity of a subclass of divisor graphs and power graphs of cyclic groups
• Grid intersection graphs and boxicity
• A survey on the boxicity and cubicity of graphs
• Bounds for boxicity of circular clique graphs and zero-divisor graphs
• A constant factor approximation algorithm for boxicity of circular arc graphs
• Boxicity and cubicity of asteroidal triple free graphs

This page was built for publication: Boxicity of graphs with bounded degree

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