Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable

DOI10.1007/S00373-019-02028-ZMaRDI QIDQ2000565zbMATH OpenOpenAlexWikidataFDO

Authors Seog-Jin Kim, Xiaowei Yu

Publication date 28 June 2019

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.08999

zbMATH Keywords

list coloringsigned graphcoloringDP-coloring

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Signed and weighted graphs (05C22) Paths and cycles (05C38)

Abstract: DP-coloring (also known as correspondence coloring) of a simple graph is a generalization of list coloring. It is known that planar graphs without 4-cycles adjacent to triangles are 4-choosable, and planar graphs without 4-cycles are DP-4-colorable. In this paper, we show that planar graphs without 4-cycles adjacent to triangles are DP-4-colorable, which is an extension of the two results above.

Recommendations

• Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable
• Every planar graph without pairwise adjacent 3-, 4-, and 5-cycle is DP-4-colorable
• Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable
• DP-4-colorability of planar graphs without adjacent cycles of given length
• Every planar graph without 5-cycles adjacent to 6-cycles is DP-4-colorable
• Planar graphs without 4-cycles and close triangles are \((2,0,0)\)-colorable
• Planar graphs without cycles of length from 4 to 7 and intersecting triangles are DP-3-colorable
• Planar graphs without 4-cycles adjacent to triangles are 4-choosable
• Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable

Cites work

• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3563170 (Why is no real title available?)
• scientific article; zbMATH DE number 1496580 (Why is no real title available?)
• A not 3-choosable planar graph without 3-cycles
• A note on a Brooks' type theorem for DP-coloring
• A sufficient condition for DP-4-colorability
• Choosability in signed planar graphs
• Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
• DP-colorings of graphs with high chromatic number
• Every planar graph is 5-choosable
• On DP-coloring of graphs and multigraphs
• Planar graphs without 4-cycles adjacent to triangles are 4-choosable
• Sharp Dirac's theorem for DP-critical graphs
• Signed graph coloring
• The 4-choosability of plane graphs without 4-cycles
• The asymptotic behavior of the correspondence chromatic number
• The chromatic number of a signed graph

Cited in

(25)

• Every planar graph without adjacent cycles of length at most 8 is 3-choosable
• Every planar graph without pairwise adjacent 3-, 4-, and 5-cycle is DP-4-colorable
• Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable
• Planar graphs without chordal 6-cycles and necklaces are DP-4-colorable
• A sufficient condition for planar graphs to be DP-4-colorable
• Relaxed DP-coloring and another generalization of DP-coloring on planar graphs without 4-cycles and 7-cycles
• DP-3-coloring of planar graphs without 4, 9-cycles and cycles of two lengths from \(\{6,7,8\}\)
• Variable degeneracy on toroidal graphs
• Combinatorial Nullstellensatz and DP-coloring of graphs
• Every planar graph without 5-cycles adjacent to 6-cycles is DP-4-colorable
• Concepts of signed graph coloring
• DP-coloring on planar graphs without given adjacent short cycles
• DP-4-colorability of planar graphs without adjacent cycles of given length
• DP-4-colorability of two classes of planar graphs
• A weak DP-coloring of planar graphs without 4- and 9-cycles
• An analogue of DP-coloring for variable degeneracy and its applications
• Variable degeneracy of planar graphs without chorded 6-cycles
• Cover and variable degeneracy
• DP-\(4\)-colorability of planar graphs without intersecting \(5\)-cycles
• Planar graphs without cycles of length from 4 to 7 and intersecting triangles are DP-3-colorable
• Planar graphs without 7-cycles and butterflies are DP-4-colorable
• A generalization of some results on list coloring and DP-coloring
• Relaxed DP-3-coloring of planar graphs without some cycles
• Multiple DP-coloring of planar graphs without 3-cycles and normally adjacent 4-cycles
• Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable

This page was built for publication: Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable

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