Boxicity and cubicity of asteroidal triple free graphs

DOI10.1016/J.DISC.2010.01.020zbMATH Open1219.05151arXiv0812.0894OpenAlexW2122913936MaRDI QIDQ968429FDOQ968429

Diptendu Bhowmick, L. Sunil Chandran

Publication date: 5 May 2010

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

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$.

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

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

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)

Cites Work

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

Cited In (2)

• Boxicity of line graphs
• 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)