论文标题
无三角形平面图的分解
Decomposition of triangle-free planar graphs
论文作者
论文摘要
图$ g $的分解是$ g $的子图的家族，其边缘集构成了$ e（g）$的分区。在本文中，我们证明，每个无三角形的平面图$ g $都可以分解为$ 2 $ - 定型图和匹配。因此，每个无三角形平面图$ g $都有一个匹配的$ m $，因此$ g-m $在线3-dp-colorant。这加强了[R. škrekovski，{\ em agrötzsch-type定理，用于列表颜色不当一}，combin。概率。计算。 8（1999），493-507]，每个不含三角形的平面图都是$ 1 $ - 提名$ 3 $ - choosable。
A decomposition of a graph $G$ is a family of subgraphs of $G$ whose edge sets form a partition of $E(G)$. In this paper, we prove that every triangle-free planar graph $G$ can be decomposed into a $2$-degenerate graph and a matching. Consequently, every triangle-free planar graph $G$ has a matching $M$ such that $G-M$ is online 3-DP-colorable. This strengthens an earlier result in [R. Škrekovski, {\em A Grötzsch-Type Theorem for List Colourings with Impropriety One}, Combin. Prob. Comput. 8 (1999), 493-507] that every triangle-free planar graph is $1$-defective $3$-choosable.
