Decomposing a planar graph without triangular 4-cycles into a matching and a 3-colorable graph

DOI10.1016/J.DAM.2019.04.026MaRDI QIDQ2274084zbMATH OpenOpenAlexWikidataFDO

Authors Ziwen Huang, Runrun Liu, Gaozhen Wang

Publication date 19 September 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2019.04.026

zbMATH Keywords

bad cyclesdischargingplanar graphsuperextension

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Decomposing a planar graph without cycles of length 5 into a matching and a 3-colorable graph
• On 3-colorable planar graphs without cycles of four lengths
• The \((3, 3)\)-colorability of planar graphs without 4-cycles and 5-cycles
• A \((2, 1)\)-decomposition of planar graphs without intersecting 3-cycles and adjacent \(4^-\)-cycles
• On 3-colorable planar graphs without prescribed cycles
• Decomposition of planar graphs without 5-cycles or K₄
• On the 3-colorability of planar graphs without 4-, 7- and 9-cycles
• A note on total colorings of planar graphs without 4-cycles
• On the 3-colorability of planar graphs without \(\{4,8,9\}\)-cycles
• On 3-colorable planar graphs without short cycles

Cites work

• A note on list improper coloring of plane graphs
• A note on list improper coloring planar graphs
• A relaxation of the Bordeaux conjecture
• A relaxation of the strong Bordeaux Conjecture
• A sufficient condition for planar graphs to be 3-colorable
• Colorings of plane graphs: a survey
• Decomposing a planar graph without cycles of length 5 into a matching and a 3-colorable graph
• Defective coloring revisited
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• scientific article; zbMATH DE number 434910 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• Improper choosability of planar graphs without 4-cycles
• On \((3,1)^*\)-coloring of plane graphs
• Planar graphs without 3-cycles adjacent to cycles of length 3 or 5 are \((3, 1)\)-colorable
• Planar graphs without cycles of length 4 or 5 are (2, 0, 0)-colorable
• Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable
• Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable
• Some simplified NP-complete graph problems
• Steinberg's conjecture is false

Cited in

(9)

• Decomposing a planar graph into degenerate graphs
• Every planar graph without triangles adjacent to cycles of length 3 or 6 is \(( 1 , 1 , 1 )\)-colorable
• Decomposition of planar graphs with forbidden configurations
• Decomposing a planar graph without cycles of length 5 into a matching and a 3-colorable graph
• Decompositions of quadrangle-free planar graphs
• A \((2, 1)\)-decomposition of planar graphs without intersecting 3-cycles and adjacent \(4^-\)-cycles
• Decomposing planar graphs without triangular short cycles into a matching and a 3-colorable graph
• The independence ratio of 4-cycle-free planar graphs
• Triangle decompositions of planar graphs

This page was built for publication: Decomposing a planar graph without triangular 4-cycles into a matching and a 3-colorable graph

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