Boxicity and maximum degree

DOI10.1016/J.JCTB.2007.08.002zbMath1136.05045arXivmath/0610262OpenAlexW2138222093MaRDI QIDQ2477634

Mathew C. Francis, L. Sunil Chandran, Naveen Sivadasan

Publication date: 14 March 2008

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0610262

zbMATH Keywords

chromatic numbermaximum degreeboxicitysquare of a graph

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (23)

Local boxicity ⋮ Covering with Euclidean boxes ⋮ Boxicity of graphs on surfaces ⋮ Geometric representation of graphs in low dimension using axis parallel boxes ⋮ Chronological rectangle digraphs which are two-terminal series-parallel ⋮ Local boxicity and maximum degree ⋮ Boxicity of line graphs ⋮ On the boxicity of Kneser graphs and complements of line graphs ⋮ Intersection dimension and graph invariants ⋮ Boxicity of leaf powers ⋮ Chordal bipartite graphs with high boxicity ⋮ Boxicity of circular arc graphs ⋮ Boxicity and cubicity of asteroidal triple free graphs ⋮ A note on the intersection property for flat boxes and boxicity in \(\mathbb R^d\) ⋮ Cubicity of interval graphs and the claw number ⋮ Cubicity, degeneracy, and crossing number ⋮ Better bounds for poset dimension and boxicity ⋮ Boxicity of graphs with bounded degree ⋮ Cubicity, boxicity, and vertex cover ⋮ Boxicity of Halin graphs ⋮ On the stab number of rectangle intersection graphs ⋮ On the cubicity of interval graphs ⋮ Lower bounds for boxicity

Cites Work

• Unnamed Item
• Computing the boxicity of a graph by covering its complement by cointerval graphs
• Interval representations of planar graphs
• A special planar satisfiability problem and a consequence of its NP- completeness
• Boxicity and treewidth
• The Complexity of the Partial Order Dimension Problem

This page was built for publication: Boxicity and maximum degree