论文标题
禁止诱导的子图在分裂图中的圆形图
Forbidden induced subgraph characterization of circle graphs within split graphs
论文作者
论文摘要
如果其顶点与一个圆圈的家族对应，则图为圆，以使每个两个不同的顶点在且仅当相应的和弦具有非空交点时相邻。尽管圆形图具有多种特征，但尚不清楚通过最小禁止诱发的子图的结构表征，甚至不仅限于拆分图（这是可以将其顶点集的图形分配为一个集团和稳定集的图形）。在这项工作中，我们通过最少禁止的圆形图的子图（仅限于拆分图）给出了表征。
A graph is circle if its vertices are in correspondence with a family of chords in a circle in such a way that every two distinct vertices are adjacent if and only if the corresponding chords have nonempty intersection. Even though there are diverse characterizations of circle graphs, a structural characterization by minimal forbidden induced subgraphs for the entire class of circle graphs is not known, not even restricted to split graphs (which are the graphs whose vertex set can be partitioned into a clique and a stable set). In this work, we give a characterization by minimal forbidden induced subgraphs of circle graphs, restricted to split graphs.
