Computing the boxicity of a graph by covering its complement by cointerval graphs

DOI10.1016/0166-218X(83)90077-XzbMath0524.05059OpenAlexW1971431042MaRDI QIDQ585228

Fred S. Roberts, Margaret B. Cozzens

Publication date: 1983

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

Full work available at URL: https://doi.org/10.1016/0166-218x(83)90077-x

zbMATH Keywords

intersection graphinterval graphboxicityedge coverings

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items (33)

Intersection dimensions of graph classes ⋮ Boxicity and treewidth ⋮ Representability and boxicity of simplicial complexes ⋮ On dimensional properties of graphs ⋮ Chronological rectangle digraphs which are two-terminal series-parallel ⋮ Matchings, coverings, and Castelnuovo-Mumford regularity ⋮ Boxicity of line graphs ⋮ Bounds on the Stanley depth and Stanley regularity of edge ideals of clutters ⋮ On the boxicity of Kneser graphs and complements of line graphs ⋮ Local and union boxicity ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ Boxicity of leaf powers ⋮ Chordal bipartite graphs with high boxicity ⋮ Boxicity of circular arc graphs ⋮ Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs ⋮ Grid intersection graphs and boxicity ⋮ Boxicity and maximum degree ⋮ Towards a comprehensive theory of conflict-tolerance graphs ⋮ Dimension-2 poset competition numbers and dimension-2 poset double competition numbers ⋮ Boxicity and cubicity of asteroidal triple free graphs ⋮ Cubicity of interval graphs and the claw number ⋮ Cubicity, degeneracy, and crossing number ⋮ The cubicity of hypercube graphs ⋮ Boxicity of graphs with bounded degree ⋮ Cubicity, boxicity, and vertex cover ⋮ An upper bound for cubicity in terms of boxicity ⋮ Bounds for the boxicity of Mycielski graphs ⋮ On the stab number of rectangle intersection graphs ⋮ On the cubicity of certain graphs ⋮ On the Computation of the Competition Number of a Graph ⋮ Lower bounds for boxicity ⋮ The relationship between the threshold dimension of split graphs and various dimensional parameters ⋮ Irrepresentability by multiple intersection, or why the interval number is unbounded

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Chronological orderings of interval graphs
• A characterization of Robert's inequality for boxicity
• On intersections of interval graphs
• The splittance of a graph
• Parallel concepts in graph theory
• Incidence matrices and interval graphs
• Intransitive indifference with unequal indifference intervals
• Representation of a finite graph by a set of intervals on the real line
• Counting Interval Graphs
• A Characterization of Comparability Graphs and of Interval Graphs

This page was built for publication: Computing the boxicity of a graph by covering its complement by cointerval graphs