Near-colorings: non-colorable graphs and NP-completeness
From MaRDI portal
Publication:2260631
zbMath1308.05052arXiv1306.0752MaRDI QIDQ2260631
Pascal Ochem, Mickaël Montassier
Publication date: 11 March 2015
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1306.0752
Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Vertex degrees (05C07)
Related Items (29)
A sufficient condition for planar graphs with girth 5 to be \((1,7)\)-colorable ⋮ 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 ⋮ 2-subcoloring is NP-complete for planar comparability graphs ⋮ Colouring planar graphs with bounded monochromatic components ⋮ Partitioning sparse graphs into an independent set and a graph with bounded size components ⋮ Path partition of planar graphs with girth at least six ⋮ Every planar graph without 4-cycles and 5-cycles is (3,3)-colorable ⋮ On the vertex partitions of sparse graphs into an independent vertex set and a forest with bounded maximum degree ⋮ Planar graphs without 5-cycles and intersecting triangles are \((1, 1, 0)\)-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 ⋮ Decomposing a triangle-free planar graph into a forest and a subcubic forest ⋮ Unnamed Item ⋮ (1,k)-Coloring of Graphs with Girth at Least Five on a Surface ⋮ Partitioning a triangle-free planar graph into a forest and a forest of bounded degree ⋮ Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests ⋮ Planar graphs with girth at least 5 are \((3, 5)\)-colorable ⋮ Every planar graph without 4-cycles and 5-cycles is \((2, 6)\)-colorable ⋮ Splitting a planar graph of girth 5 into two forests with trees of small diameter ⋮ Maximum average degree and relaxed coloring ⋮ Planar graphs without 4-cycles and close triangles are \((2,0,0)\)-colorable ⋮ On the vertex partition of planar graphs into forests with bounded degree ⋮ Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths ⋮ Vertex partitions of \((C_3, C_4, C_6)\)-free planar graphs ⋮ 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
Cites Work
- Unnamed Item
- Unnamed Item
- On 1-improper 2-coloring of sparse graphs
- Improper coloring of sparse graphs with a given girth. I: \((0,1)\)-colorings of triangle-free graphs
- \((k,1)\)-coloring of sparse graphs
- \((k,j)\)-coloring of sparse graphs
- Planar graphs with girth at least 5 are \((3, 5)\)-colorable
- Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1
- Some simplified NP-complete graph problems
- Every planar map is four colorable. I: Discharging
- Every planar map is four colorable. II: Reducibility
- Subcolorings and the subchromatic number of a graph
- Defective 2-colorings of sparse graphs
- Path partitions of planar graphs
- Limits of Near-Coloring 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
- List Improper Colourings of Planar Graphs
- Graph Subcolorings: Complexity and Algorithms
- A Complexity Dichotomy for the Coloring of Sparse Graphs
- Improper choosability of graphs and maximum average degree
This page was built for publication: Near-colorings: non-colorable graphs and NP-completeness
