Boxicity and maximum degree

DOI10.1016/j.jctb.2007.08.002zbMath1136.05045arXivmath/0610262MaRDI 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 number; maximum degree; boxicity; square of a graph

Mathematics Subject Classification ID

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

Related Items

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

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