Defective 2-colorings of planar graphs without 4-cycles and 5-cycles

DOI10.1016/j.disc.2018.04.024zbMath1388.05072arXiv1611.10239OpenAlexW2558674025WikidataQ129811918 ScholiaQ129811918MaRDI QIDQ1637126

Pongpat Sittitrai, Kittikorn Nakprasit

Publication date: 7 June 2018

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

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

zbMATH Keywords

cycleplanar graphdefective coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Related Items (10)

Every planar graph without 4-cycles and 5-cycles is (3,3)-colorable ⋮ The \((3, 3)\)-colorability of planar graphs without 4-cycles and 5-cycles ⋮ Partitioning planar graphs without 4-cycles and 5-cycles into two forests with a specific condition ⋮ A weak DP-partitioning of planar graphs without 4-cycles and 6-cycles ⋮ Graph partitions under average degree constraint ⋮ Unnamed Item ⋮ Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests ⋮ Every planar graph without 4-cycles and 5-cycles is \((2, 6)\)-colorable ⋮ DP-4-colorability of planar graphs without adjacent cycles of given length ⋮ Partitioning planar graphs without 4-cycles and 6-cycles into a linear forest and a forest

Cites Work

• Unnamed Item
• Steinberg's conjecture is false
• Planar graphs with girth at least 5 are \((3, 5)\)-colorable
• Every planar graph with cycles of length neither 4 nor 5 is \((1,1,0)\)-colorable
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Near-colorings: non-colorable graphs and NP-completeness
• Defective 2-colorings of sparse graphs
• (1,k)-Coloring of Graphs with Girth at Least Five on a Surface
• Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Improper choosability of graphs and maximum average degree

This page was built for publication: Defective 2-colorings of planar graphs without 4-cycles and 5-cycles