Representing graphs as the intersection of cographs and threshold graphs (Q2040010)

Summary: 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)\cap\cdots\cap E(G_k)\). For a graph \(G, \dim_{COG}(G)\) (resp. \( \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) \( \dim_{COG}(G)\leqslant\text{tw}(G)+2\), (b) \( \dim_{TH}(G)\leqslant\text{pw}(G)+1\), and (c) \( \dim_{TH}(G)\leqslant\chi(G)\cdot\text{box}(G)\), where \(\text{tw}(G), \text{pw}(G), \chi(G)\) and \(\text{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 \(\dim_{COG}(G)\) and \(\dim_{TH}(G)\) when \(G\) belongs to some special graph classes.