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

DOI10.1016/j.dam.2019.04.026zbMath1419.05177OpenAlexW2946634956WikidataQ127830342 ScholiaQ127830342MaRDI QIDQ2274084

Ziwen Huang, Gaozhen Wang, Runrun Liu

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

planar graphbad cyclesdischargingsuperextension

Mathematics Subject Classification ID

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

Related Items (1)

Every planar graph without triangles adjacent to cycles of length 3 or 6 is \(( 1 , 1 , 1 )\)-colorable

Cites Work

• Unnamed Item
• Unnamed Item
• Steinberg's conjecture is false
• Decomposing a planar graph without cycles of length 5 into a matching and a 3-colorable graph
• Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable
• Planar graphs without cycles of length 4 or 5 are \((2, 0, 0)\)-colorable
• Planar graphs without 5-cycles and intersecting triangles are \((1, 1, 0)\)-colorable
• A note on list improper coloring of plane graphs
• Some simplified NP-complete graph problems
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• A sufficient condition for planar graphs to be 3-colorable
• Planar graphs without 3-cycles adjacent to cycles of length 3 or 5 are \((3, 1)\)-colorable
• Colorings of plane graphs: a survey
• A relaxation of the Bordeaux conjecture
• Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable
• Defective coloring revisited
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• A relaxation of the strong Bordeaux Conjecture
• On $(3,1)^*$-Coloring of Plane Graphs
• Improper Choosability of Planar Graphs without 4-Cycles
• A note on list improper coloring planar graphs

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