标题： 具有局部完全2边着色的图及其与恰当圆弧图的关系 显示英文标题

标题： On graphs which have locally complete 2-edge-colourings and their relationship to proper circular-arc graphs

摘要： 一个2边着色图$G$被称为{\bf 局部完备}，如果对于每个顶点$v$，通过相同颜色的边与$v$相邻的顶点在$G$中诱导出一个完全子图。局部完全的2边着色图具有良好的性质，并且存在一个多项式算法来判断这样的图是否具有交替哈密顿环，其中交替意味着环上两个连续边的颜色不同。在本文中，我们证明具有局部完全2边着色的图可以在多项式时间内被识别。我们给出了这一类图的禁止子结构特征，类似于Gallai对补比较图的特征描述。最后，我们通过禁止子图表征了具有局部完全2边着色的恰当区间图和恰当圆弧图。 显示英文摘要

摘要： A 2-edge-coloured graph $G$ is called {\bf locally complete} if for each vertex $v$, the vertices adjacent to $v$ through edges of the same colour induce a complete subgraph in $G$. Locally complete 2-edge-coloured graphs have nice properties and there exists a polynomial algorithm to decide whether such a graph has an alternating hamiltonian cycle, where alternating means that the colour of two consecutive edges on the cycle are different. In this paper we show that graphs having locally complete 2-edge-colourings can be recognized in polynomial time. We give a forbidden substructure characterization for this class of graphs analogous to Gallai's characterization for cocomparability graphs. Finally, we characterize proper interval graphs and proper circular-arc graphs which have locally complete 2-edge-colourings by forbidden subgraphs.