Decomposition of triangle-free planar graphs

arXiv2207.09659MaRDI QIDQ6405504FDOQ6405504

Rongxing Xu, Xuding Zhu

Publication date: 20 July 2022

Abstract: 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. v{S}krekovski, {em A Gr"{o}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.

This page was built for publication: Decomposition of triangle-free planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6405504)