Boxicity and cubicity of asteroidal triple free graphs

DOI10.1016/j.disc.2010.01.020zbMath1219.05151arXiv0812.0894OpenAlexW2122913936MaRDI QIDQ968429

Diptendu Bhowmick, L. Sunil Chandran

Publication date: 5 May 2010

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

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

zbMATH Keywords

chromatic numberboxicitycubicityasteroidal triple free graphchordal dimensionclaw number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75)

Related Items (2)

Chronological rectangle digraphs which are two-terminal series-parallel ⋮ Boxicity of line graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing the boxicity of a graph by covering its complement by cointerval graphs
• Grid intersection graphs and boxicity
• Geometric representation of graphs in low dimension using axis parallel boxes
• Boxicity of graphs with bounded degree
• Cubicity, boxicity, and vertex cover
• On the cubicity of certain graphs
• Interval representations of planar graphs
• Poset boxicity of graphs
• The circular dimension of a graph
• A special planar satisfiability problem and a consequence of its NP- completeness
• Characterizations and algorithmic applications of chordal graph embeddings
• A functional equation that arises in problems of scheduling with priorities and lateness/earliness penalties
• Triangulating graphs without asteroidal triples
• Lower bounds for boxicity
• Boxicity and maximum degree
• Boxicity and treewidth
• Cubicity of Interval Graphs and the Claw Number
• The Complexity of the Partial Order Dimension Problem
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• Asteroidal Triple-Free Graphs
• On the chordality of a graph
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs

This page was built for publication: Boxicity and cubicity of asteroidal triple free graphs