论文标题
将图表示为Cobhaphs和阈值图的相交
Representing graphs as the intersection of cographs and threshold graphs
论文作者
论文摘要
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)$.对于图$ g $，$ \ mathrm {dim} _ {cog}（g）$（resp。$ \ mathrm {dim} _ {th}（g）$）表示其相交相交给出$ g $ g $的Cographss（reshold threshold Graphs）的最小数量（分别阈值图）。我们在这些参数上为通用图以及一些特殊的图形介绍了几个新界限。显示出任何图表$ g $：（a）$ \ mathrm {dim} _ {cog}（g）\ leq \ leq \ mathrm {tw}（g）+2 $，（b）$ \ mathrm {dim} _ {dim} _ {th} _ {th}（g）美元图形$ g $的路径宽，色数和箱形。我们还得出了这些循环的这些参数的确切值，并表明每个森林都是两个Cographs的相交。这些结果使我们能够在$ \ mathrm {dim} _ {cog}（g）$和$ \ mathrm {dim} _ {th}（g）$上得出改进的界限。
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$, $\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)\leq\mathrm{tw}(G)+2$, (b) $\mathrm{dim}_{TH}(G)\leq\mathrm{pw}(G)+1$, and (c) $\mathrm{dim}_{TH}(G)\leqχ(G)\cdot\mathrm{box}(G)$, where $\mathrm{tw}(G)$, $\mathrm{pw}(G)$, $χ(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.
