(1,k)-Coloring of Graphs with Girth at Least Five on a Surface

DOI10.1002/jgt.22039zbMath1359.05099arXiv1412.0344OpenAlexW2963767765MaRDI QIDQ2978189

Hojin Choi, Geewon Suh, Ilkyoo Choi, Jisu Jeong

Publication date: 21 April 2017

Published in: Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

graphs on surfacesdischargingimproper coloring

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Vertex degrees (05C07)

Related Items (12)

Every planar graph with girth at least 5 is \((1,9)\)-colorable ⋮ Defective 2-colorings of planar graphs without 4-cycles and 5-cycles ⋮ Characterization of Cycle Obstruction Sets for Improper Coloring Planar Graphs ⋮ Partitioning sparse graphs into an independent set and a graph with bounded size components ⋮ 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 bounded degree forests ⋮ Every planar graph without 4-cycles and 5-cycles is \((2, 6)\)-colorable ⋮ Near-colorings: non-colorable graphs and NP-completeness ⋮ Planar graphs with girth at least 5 are \((3, 4)\)-colorable ⋮ An \((F_3,F_5)\)-partition of planar graphs with girth at least 5 ⋮ Partitioning planar graphs without 4-cycles and 6-cycles into a linear forest and a forest

Cites Work

• Unnamed Item
• On 1-improper 2-coloring of sparse graphs
• \((k,1)\)-coloring of sparse graphs
• \((k,j)\)-coloring of sparse graphs
• Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• List improper colorings of planar graphs with prescribed girth
• Near-colorings: non-colorable graphs and NP-completeness
• Defective 2-colorings of sparse graphs
• Path partitions of planar graphs
• 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
• List Improper Colourings of Planar Graphs
• A Complexity Dichotomy for the Coloring of Sparse Graphs
• Improper choosability of graphs and maximum average degree

This page was built for publication: (1,k)-Coloring of Graphs with Girth at Least Five on a Surface