A graph $G$ is said to be the intersection of graphs $G_1,G_2,ldots,G_k$ if $V(G)=V(G_1)=V(G_2)=cdots=V(G_k)$ and $E(G)=E(G_1)cap E(G_2)capcdotscap E(G_k)$. For a graph $G$, $mathrm{dim}_{COG}(G)$ (resp. $mathrm{dim}_{TH}(G)$) denotes the minimum number of cographs (resp. threshold graphs) whose intersection gives $G$. We present several new bounds on these parameters for general graphs as well as some special classes of graphs. It is shown that for any graph $G$: (a) $mathrm{dim}_{COG}(G)leqmathrm{tw}(G)+2$, (b) $mathrm{dim}_{TH}(G)leqmathrm{pw}(G)+1$, and (c) $mathrm{dim}_{TH}(G)leqchi(G)cdotmathrm{box}(G)$, where $mathrm{tw}(G)$, $mathrm{pw}(G)$, $chi(G)$ and $mathrm{box}(G)$ denote respectively the treewidth, pathwidth, chromatic number and boxicity of the graph $G$. We also derive the exact values for these parameters for cycles and show that every forest is the intersection of two cographs. These results allow us to derive improved bounds on $mathrm{dim}_{COG}(G)$ and $mathrm{dim}_{TH}(G)$ when $G$ belongs to some special graph classes.
تحميل البحث