DP-3-coloring of planar graphs without certain cycles
From MaRDI portal
Publication:2022504
Abstract: DP-coloring is a generalization of list coloring, which was introduced by Dvov{r}'{a}k and Postle [J. Combin. Theory Ser. B 129 (2018) 38--54]. Zhang [Inform. Process. Lett. 113 (9) (2013) 354--356] showed that every planar graph with neither adjacent triangles nor 5-, 6-, 9-cycles is 3-choosable. Liu et al. [Discrete Math. 342 (2019) 178--189] showed that every planar graph without 4-, 5-, 6- and 9-cycles is DP-3-colorable. In this paper, we show that every planar graph with neither adjacent triangles nor 5-, 6-, 9-cycles is DP-3-colorable, which generalizes these results. Yu et al. gave three Bordeaux-type results by showing that (i) every planar graph with the distance of triangles at least three and no 4-, 5-cycles is DP-3-colorable; (ii) every planar graph with the distance of triangles at least two and no 4-, 5-, 6-cycles is DP-3-colorable; (iii) every planar graph with the distance of triangles at least two and no 5-, 6-, 7-cycles is DP-3-colorable. We also give two Bordeaux-type results in the last section: (i) every plane graph with neither 5-, 6-, 8-cycles nor triangles at distance less than two is DP-3-colorable; (ii) every plane graph with neither 4-, 5-, 7-cycles nor triangles at distance less than two is DP-3-colorable.
Recommendations
- DP-3-coloring of planar graphs without 4, 9-cycles and cycles of two lengths from \(\{6,7,8\}\)
- Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable
- Planar graphs without cycles of length from 4 to 7 and intersecting triangles are DP-3-colorable
- Every planar graph without pairwise adjacent 3-, 4-, and 5-cycle is DP-4-colorable
- DP-4-colorability of planar graphs without adjacent cycles of given length
Cites work
- 3-choosability of triangle-free planar graphs with constraints on 4-cycles
- 3-list-coloring planar graphs of girth 5
- A note on 3-choosability of planar graphs
- A note on 3-choosability of planar graphs
- A note on 3-choosability of planar graphs
- A note on 3-choosability of planar graphs related to Montanssier's conjecture
- A note on 3-choosability of planar graphs without certain cycles
- A sufficient condition for a planar graph to be 3-choosable
- A sufficient condition for DP-4-colorability
- Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
- Corrigendum to ``On 3-choosability of planar graphs with neither adjacent triangles nor 5-, 6- and 9-cycles
- DP-3-coloring of planar graphs without 4, 9-cycles and cycles of two lengths from \(\{6,7,8\}\)
- DP-3-coloring of some planar graphs
- DP-4-colorability of two classes of planar graphs
- Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable
- Every planar graph without adjacent cycles of length at most 8 is 3-choosable
- scientific article; zbMATH DE number 6718589 (Why is no real title available?)
- scientific article; zbMATH DE number 5983740 (Why is no real title available?)
- scientific article; zbMATH DE number 3735847 (Why is no real title available?)
- scientific article; zbMATH DE number 6172651 (Why is no real title available?)
- On 3-choosability of planar graphs without certain cycles
- On 3-choosability of plane graphs having no 3-, 6-, 7- and 8-cycles
- On 3-choosability of plane graphs without 6-, 7- and 9-cycles
- Planar graphs without 3-, 7-, and 8-cycles are 3-choosable
- Planar graphs without cycles of length 4, 5, 8, or 9 are 3-choosable
- Planar graphs without cycles of length 4, 7, 8, or 9 are 3-choosable
- Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable
- The 3-choosability of plane graphs of girth 4
Cited in
(8)- DP-4-coloring of planar graphs with some restrictions on cycles
- DP-3-coloring of planar graphs without 4, 9-cycles and cycles of two lengths from \(\{6,7,8\}\)
- Sufficient conditions on planar graphs to have a relaxed DP-3-coloring
- Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable
- Weak degeneracy of planar graphs without 4- and 6-cycles
- A weak DP-coloring of planar graphs without 4- and 9-cycles
- Planar graphs having no cycle of length 4, 7, or 9 are DP-3-colorable
- Planar graphs that exclude \(\{4, 5, 7, 8\}\)-cycles and intersecting triangles are DP-3-colorable
This page was built for publication: DP-3-coloring of planar graphs without certain cycles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2022504)
