几类IC-平面图的退化性

Degeneracy of Some Classes of IC-Planar Graphs

若图G的每一个子图H都有δ(H) ≤ k, 则称G是k-退化的. 根据不含k-圈(k ∈ {3, 5, 6})的平面图是3-退化的, 本文证明了不含k-圈的IC-平面图是4-退化的. 本文还进一步证明了3-圈与4-圈不相邻, 3-圈与5-圈不相邻或4-圈与4-圈不相邻的IC-平面图也是4-退化的. 同时, 本文给出了不含k-圈(k ∈ {3, 4, 5, 6})且4-正则的IC-平面图的例子。

If every subgraph H of graph G has δ(H) ≤ k, then G is k-degenerate. A planar graph without k-cycles (k ∈ {3, 5, 6}) is 3-degenerate, this paper proves that an IC- planar graph without k-cycles is 4-degenerate. This paper is further proved that the IC-planar graph with 3-cycle not adjacent to 4-cycle, 3-cycle not adjacent to 5-cycle or 4-cycle not adjacent to 4-cycle is also 4-degenerate. And we give an example of 4-regular IC-planar graphs without k-cycles (k ∈ {3, 4, 5, 6}).