几类IC-平面图的退化性
Degeneracy of Some Classes of IC-Planar Graphs
DOI: 10.12677/AAM.2021.1010356, PDF, HTML, 下载: 265  浏览: 386 
作者: 田鸿珲：浙江师范大学，数学与计算机科学学院，浙江 金华
关键词: IC-平面图；退化性；权转移；IC-Planar Graph； Degeneracy； Discharging
摘要: 若图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-平面图的例子。
Abstract: 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}).
文章引用：田鸿珲. 几类IC-平面图的退化性[J]. 应用数学进展, 2021, 10(10): 3390-3398. https://doi.org/10.12677/AAM.2021.1010356

参考文献

[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

为你推荐