论文标题
图形类等效于12个呈现图
Graph classes equivalent to 12-representable graphs
论文作者
论文摘要
琼斯等。 （2015年）介绍了$ u $ - 代表图的概念，其中$ u $是$ \ {1，2 \} $与$ 22 \ cdots2 $不同的单词，作为单词可说明图的概括。 Kitaev（2016）表明，如果$ u $的长度至少为3，则每个图都是$ u $ - 代表。这表明在$ u $呈现图的理论中只有两个非平凡的类：11个可说的图形，它们对应于单词说明的图形，而12个可说明图表。这项研究涉及12个代表的图。 琼斯等。 （2015年）根据禁止的诱导子图，对12棵可陈述的树进行了特征。 Chen and Kitaev（2022）提出了一个禁止诱发的次级图表，该子类是12个陈述的网格图。 本文表明，当且仅当它是一个间隔围栏bigraph时，两部分图是可以说的12个。等效性为我们提供了12个可呈现的两分图的禁止引起的子图表征，因为最小禁止诱导的子图的列表以间隔封存bigraphs而闻名。然后，我们对网格图具有禁止的诱导子图表征，该表格解决了Chen和Kitaev的开放问题（2022）。该研究还表明，当且仅当它是简单三角形图的补充时，图是12个呈现的。这种等价表明，琼斯等人提出的12个陈述性的必要条件。 （2015年）也足够了。最后，我们从这些等价中表明，可以在$ o（n^2）$中确定12-值的性能的时间，以及$ o（n（\ bar {m}+n））$用于任意图的时间，其中$ n $和$ n $ and $ \ bar {m} $是给定图表的角度和辅助图的数量。
Jones et al. (2015) introduced the notion of $u$-representable graphs, where $u$ is a word over $\{1, 2\}$ different from $22\cdots2$, as a generalization of word-representable graphs. Kitaev (2016) showed that if $u$ is of length at least 3, then every graph is $u$-representable. This indicates that there are only two nontrivial classes in the theory of $u$-representable graphs: 11-representable graphs, which correspond to word-representable graphs, and 12-representable graphs. This study deals with 12-representable graphs. Jones et al. (2015) provided a characterization of 12-representable trees in terms of forbidden induced subgraphs. Chen and Kitaev (2022) presented a forbidden induced subgraph characterization of a subclass of 12-representable grid graphs. This paper shows that a bipartite graph is 12-representable if and only if it is an interval containment bigraph. The equivalence gives us a forbidden induced subgraph characterization of 12-representable bipartite graphs since the list of minimal forbidden induced subgraphs is known for interval containment bigraphs. We then have a forbidden induced subgraph characterization for grid graphs, which solves an open problem of Chen and Kitaev (2022). The study also shows that a graph is 12-representable if and only if it is the complement of a simple-triangle graph. This equivalence indicates that a necessary condition for 12-representability presented by Jones et al. (2015) is also sufficient. Finally, we show from these equivalences that 12-representability can be determined in $O(n^2)$ time for bipartite graphs and in $O(n(\bar{m}+n))$ time for arbitrary graphs, where $n$ and $\bar{m}$ are the number of vertices and edges of the complement of the given graph.
