On a special class of boxicity 2 graphs

DOI10.1007/978-3-319-14974-5_16MaRDI QIDQ5174960zbMATH OpenOpenAlexFDO

Authors Sujoy Bhore, Dibyayan Chakraborty, Sandip Das, Sagnik Sen

Publication date 19 February 2015

Published in Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

geometric intersection graphinterval graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: We define and study a class of graphs, called 2-stab interval graphs (2SIG), with boxicity 2 which properly contains the class of interval graphs. A 2SIG is an axes-parallel rectangle intersection graph where the rectangles have unit height (that is, length of the side parallel to $Y$-axis) and intersects either of the two fixed lines, parallel to the $X$-axis, distance $1+epsilon$ ($0<epsilon<1$) apart. Intuitively, 2SIG is a graph obtained by putting some edges between two interval graphs in a particular rule. It turns out that for these kind of graphs, the chromatic number of any of its induced subgraphs is bounded by twice of its (induced subgraph) clique number. This shows that the graph, even though not perfect, is not very far from it. Then we prove similar results for some subclasses of 2SIG and provide efficient algorithm for finding their clique number. We provide a matrix characterization for a subclass of 2SIG graph.

Recommendations

• On rectangle intersection graphs with stab number at most two
• On rectangle intersection graphs with stab number at most two
• On the stab number of rectangle intersection graphs
• Characterization of the graphs with boxicity \(\leq 2\)
• On local structures of cubicity 2 graphs

Cited in

(9)

• The box-TDI system associated with 2-edge connected spanning subgraphs
• Characterization of the graphs with boxicity \(\leq 2\)
• On local structures of cubicity 2 graphs
• SIG-dimensional of \(K_{2,2}\)-free graphs
• scientific article; zbMATH DE number 5214885 (Why is no real title available?)
• On rectangle intersection graphs with stab number at most two
• On rectangle intersection graphs with stab number at most two
• On the stab number of rectangle intersection graphs
• On (2,3)-agreeable box societies

This page was built for publication: On a special class of boxicity 2 graphs

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