论文标题
$ k_3 $ - 免费图形和两部分图
Biclique Graphs of $K_3$-free Graphs and Bipartite Graphs
论文作者
论文摘要
图形的双晶体是最大的完整双方子图。 $ g $，$ kb（g）$的双曲（定义为$ g $的双相的相交图）在2010年被引入和表征。但是，此特征并未导致多项式时间识别算法。其识别问题的时间复杂性保持开放。当限制某些课程时，有一些关于此问题的作品。在这项工作中，我们给出了$ k_3 $ - free Graph $ g $的双形图的特征。我们证明$ kb（g）$是特定图的方形图，我们称之为互联的$ g $（$ kb_m（g）$）。尽管它不会导致多项式时间识别算法，但它提供了一种新工具，可以使用方形图的已知属性证明Biclique图（仅限于$ K_3 $ free Graphs）的属性。例如，我们将有关诱发$ {p_3}'$ s的属性概括为有关星星的属性，并证明了Groshaus和Montero发布的猜想，仅限于$ k_3 $ free Graphs。我们还表征了两分图的比克利克图类。我们证明$ kb（$ bipartite $）=（$ iic可稳定性$）^2 $，其中IIC可比性是我们称之为Intervalsection Intervalsection封闭可比性的可比性图的子类。
A biclique of a graph is a maximal complete bipartite subgraph. The biclique graph of a graph $G$, $KB(G)$, defined as the intersection graph of the bicliques of $G$, was introduced and characterized in 2010. However, this characterization does not lead to polynomial time recognition algorithms. The time complexity of its recognition problem remains open. There are some works on this problem when restricted to some classes. In this work we give a characterization of the biclique graph of a $K_3$-free graph $G$. We prove that $KB(G)$ is the square graph of a particular graph which we call Mutually Included Biclique Graph of $G$ ($KB_m(G)$). Although it does not lead to a polynomial time recognition algorithm, it gives a new tool to prove properties of biclique graphs (restricted to $K_3$-free graphs) using known properties of square graphs. For instance we generalize a property about induced ${P_3}'$s in biclique graphs to a property about stars and proved a conjecture posted by Groshaus and Montero, when restricted to $K_3$-free graphs. Also we characterize the class of biclique graphs of bipartite graphs. We prove that $KB($bipartite$) = ($IIC-comparability$)^2$, where IIC-comparability is a subclass of comparability graphs that we call Interval Intersection Closed Comparability.
