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

DOI10.1016/J.DISC.2020.111846MaRDI QIDQ2174590zbMATH OpenOpenAlexFDO

Authors Ziwen Huang

Publication date 21 April 2020

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2020.111846

zbMATH Keywords

bad cycledischargingplanar graphsuperextension

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Planar graphs without adjacent cycles of length at most five are (1,1,0)-colorable
• Planar graphs without 3-cycles adjacent to cycles of length 3 or 5 are \((3, 1)\)-colorable
• Every planar graph without 3-cycles adjacent to 4-cycles and without 6-cycles is (1, 1, 0)-colorable
• Every planar graph without cycles of length 4 or 9 is \((1, 1, 0)\)-colorable

Cites work

• A note on list improper coloring of plane graphs
• A note on list improper coloring planar graphs
• 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
• Decomposing a planar graph without triangular 4-cycles into a matching and a 3-colorable graph
• Defective coloring revisited
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• 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 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

(3)

• Decomposing planar graphs without triangular short cycles into a matching and a 3-colorable graph
• The independence ratio of 4-cycle-free planar graphs
• Planar graphs without adjacent cycles of length at most five are (1,1,0)-colorable

This page was built for publication: Every planar graph without triangles adjacent to cycles of length 3 or 6 is \(( 1 , 1 , 1 )\)-colorable

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