|
|
几类IC-平面图的退化性
|
Abstract:
若图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}).
| [1] | Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. North-Holland, New York. |
| [2] | Ringel, G. (1965) Ein Sechsfarben problem auf der Kugel. Abhandlungen aus dem Mathema- tischen Seminar der Universit¨at Hamburg, 29, 107-117. (In German) https://doi.org/10.1007/BF02996313 |
| [3] | Alberson, M. (2008) Chromatic Number, Independent Ratio, and Crossing Number. Ars Math- ematica Contemporanea, 1, 1-6. https://doi.org/10.26493/1855-3974.10.2d0 |
| [4] | Kral, D. and Stacho, L. (2010) Coloring Plane Graphs with Independent Crossings. Journal of Graph Theory, 64, 184-205. https://doi.org/10.1002/jgt.20448 |
| [5] | Wang, W. and Lih, K.W. (2002) Choosability and Edge Choosability Planar Graphs without Five Cycles. Applied Mathematics Letters, 15, 561-565. https://doi.org/10.1016/S0893-9659(02)80007-6 |
| [6] | Fijavz, G., Juvan, M., Mohar, B. and Skrekovski, R. (2002) Planar Graphs without Cycles of Specific Lengths. European Journal of Combinatorics, 23, 377-388. https://doi.org/10.1006/eujc.2002.0570 |
