Boxicity and cubicity of asteroidal triple free graphs

DOI10.1016/J.DISC.2010.01.020MaRDI QIDQ968429zbMATH OpenOpenAlexFDO

Authors 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)

Abstract: An axis parallel $d$-dimensional box is the Cartesian product $R_{1}imes{R}_{2}imes\mathrm{...}imes{R}_d$ where each $R_i$ is a closed interval on the real line. The {it boxicity} of a graph $G$, denoted as $$, is the minimum integer $d$ such that $G$ can be represented as the intersection graph of a collection of $d$-dimensional boxes. An axis parallel unit cube in $d$-dimensional space or a $d$-cube is defined as the Cartesian product $R_{1}imes{R}_{2}imes\mathrm{...}imes{R}_d$ where each $R_i$ is a closed interval on the real line of the form $[a_i,a_i+1]$. The {it cubicity} of $G$, denoted as $cub(G)$, is the minimum integer $d$ such that $G$ can be represented as the intersection graph of a collection of $d$-cubes. Let $S(m)$ denote a star graph on $m+1$ nodes. We define {it claw number} of a graph $G$ as the largest positive integer $k$ such that $S(k)$ is an induced subgraph of $G$ and denote it as $claw$. Let $G$ be an AT-free graph with chromatic number $chi(G)$ and claw number $claw$. In this paper we will show that $$ and this bound is tight. We also show that $$ $leq$ $chi(G)(ceillo{g}_{2}claw+2)$. If $G$ is an AT-free graph having girth at least 5 then $$ and therefore $cub(G)leq2ceillo{g}_{2}claw+4$.

Recommendations

• Cubicity of interval graphs and the claw number
• An upper bound for cubicity in terms of boxicity
• Cubicity of interval graphs and the claw number
• Cubicity, boxicity, and vertex cover
• Upper bound on cubicity in terms of boxicity for graphs of low chromatic number

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3737705 (Why is no real title available?)
• scientific article; zbMATH DE number 1472165 (Why is no real title available?)
• scientific article; zbMATH DE number 3307331 (Why is no real title available?)
• A functional equation that arises in problems of scheduling with priorities and lateness/earliness penalties
• A special planar satisfiability problem and a consequence of its NP- completeness
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Asteroidal Triple-Free Graphs
• Boxicity and maximum degree
• Boxicity and treewidth
• Boxicity of graphs with bounded degree
• Characterizations and algorithmic applications of chordal graph embeddings
• Computing the boxicity of a graph by covering its complement by cointerval graphs
• Cubicity of interval graphs and the claw number
• Cubicity, boxicity, and vertex cover
• Geometric representation of graphs in low dimension using axis parallel boxes
• Grid intersection graphs and boxicity
• Interval representations of planar graphs
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• Lower bounds for boxicity
• On the chordality of a graph
• On the cubicity of certain graphs
• Poset boxicity of graphs
• The Complexity of the Partial Order Dimension Problem
• The circular dimension of a graph
• Triangulating graphs without asteroidal triples

Cited in

(4)

• Boxicity of line graphs
• Cubicity of interval graphs and the claw number
• Upper bound on cubicity in terms of boxicity for graphs of low chromatic number
• Chronological rectangle digraphs which are two-terminal series-parallel

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q968429)