论文标题
圆形和间隔图上某些问题的结构表征
Structural characterization of some problems on circle and interval graphs
论文作者
论文摘要
如果圆圈中有一个和弦家族，则图是圆圈，如果相应的和弦相互交叉，则两个顶点是相邻的。圆形图有各种特征，其中许多使用局部补充或分裂分解的概念。但是，没有最小的禁止诱导子图的结构表征，用于圆形图。在本文中，我们通过在拆分图内禁止圆形图的禁止感应子图进行了表征。如果其列的排列，则$（0,1）$ - 矩阵具有连续的属性（C1P），以使每行的$ 1 $ s均一致显示。在本论文中，我们通过禁止的$（0,1）$ - 矩阵与C1P的禁止子配置来开发特征，在某些邻接关系下，行可$ 2 $ 2 $ 2 $ - 我们在结构上表征了一些由这些特殊矩阵产生的辅助圆形图。给定图形类别$π$，图$ g =（v，e）$的$π$ - completion是图$ h =（v，e \ cup f）$，这样$ h $属于$π$。如果$ h'=（v，e \ cup f'）$不属于每一个适当的子集$ f'$ of $ f $，则$π$ - $ h $的$ g $是最小的。 $ g $ $ g $的$π$ - 如果对于$ g $的每一个$π$ - completion $ h'=（v，e \ cup f'）$，则$ g $的$ f $小于或等于$ f'$的红衣主教。在本论文中，我们研究了最少完成的问题以在输入为间隔图时获得适当的间隔图。我们发现在这种特殊情况下完成最少完成的必要条件，并为未来留下一些猜想。
A graph is circle if there is a family of chords in a circle such that two vertices are adjacent if the corresponding chords cross each other. There are diverse characterizations of circle graphs, many of them using the notions of local complementation or split decomposition. However, there are no known structural characterization by minimal forbidden induced subgraphs for circle graphs. In this thesis, we give a characterization by forbidden induced subgraphs of circle graphs within split graphs. A $(0,1)$-matrix has the consecutive-ones property (C1P) for the rows if there is a permutation of its columns such that the $1$'s in each row appear consecutively. In this thesis, we develop characterizations by forbidden subconfigurations of $(0,1)$-matrices with the C1P for which the rows are $2$-colorable under a certain adjacency relationship, and we characterize structurally some auxiliary circle graph subclasses that arise from these special matrices. Given a graph class $Π$, a $Π$-completion of a graph $G = (V,E)$ is a graph $H = (V, E \cup F)$ such that $H$ belongs to $Π$. A $Π$-completion $H$ of $G$ is minimal if $H'= (V, E \cup F')$ does not belong to $Π$ for every proper subset $F'$ of $F$. A $Π$-completion $H$ of $G$ is minimum if for every $Π$-completion $H' = (V, E \cup F')$ of $G$, the cardinal of $F$ is less than or equal to the cardinal of $F'$. In this thesis, we study the problem of completing minimally to obtain a proper interval graph when the input is an interval graph. We find necessary conditions that characterize a minimal completion in this particular case, and we leave some conjectures for the future.
