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

Local boxicity, 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