A Complexity Dichotomy for the Coloring of Sparse Graphs
From MaRDI portal
Publication:4920652
DOI10.1002/jgt.21659zbMath1264.05049OpenAlexW1548527711MaRDI QIDQ4920652
Alexandre Pinlou, Pascal Ochem, Mickaël Montassier, Louis Esperet
Publication date: 21 May 2013
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/jgt.21659
Related Items (16)
Modulo orientations and matchings in graphs ⋮ Characterization of Cycle Obstruction Sets for Improper Coloring Planar Graphs ⋮ Partitioning sparse graphs into an independent set and a graph with bounded size components ⋮ Improper coloring of sparse graphs with a given girth. I: \((0,1)\)-colorings of triangle-free graphs ⋮ Sparse critical graphs for defective DP-colorings ⋮ Unnamed Item ⋮ (1,k)-Coloring of Graphs with Girth at Least Five on a Surface ⋮ On 2-defective DP-colorings of sparse graphs ⋮ Defective DP-colorings of sparse multigraphs ⋮ Defective DP-colorings of sparse simple graphs ⋮ Near-colorings: non-colorable graphs and NP-completeness ⋮ Improper Coloring of Sparse Graphs with a Given Girth, II: Constructions ⋮ Vertex partitions of \((C_3, C_4, C_6)\)-free planar graphs ⋮ Complexity of planar signed graph homomorphisms to cycles ⋮ Vertex Partitions into an Independent Set and a Forest with Each Component Small ⋮ Complexity dichotomy for oriented homomorphism of planar graphs with large girth
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1
- A simplified NP-complete satisfiability problem
- Acyclic 3-choosability of planar graphs with no cycles of length from 4 to 11
- On the complexity of \(H\)-colouring planar graphs
- Some counterexamples associated with the three-color problem
- Some simplified NP-complete graph problems
- A minor-monotone graph parameter based on oriented matroids
- Homomorphisms from sparse graphs with large girth.
- Planar graphs without cycles of length from 4 to 7 are 3-colorable
- A note on the three color problem
- Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion)
- High-girth graphs avoiding a minor are nearly bipartite
- Sachs' linkless embedding conjecture
- On the invariance of Colin de Verdière's graph parameter under clique sums
- On a minor-monotone graph invariant
- Path partitions of planar graphs
- Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k
- Acyclic Colourings of Planar Graphs with Large Girth
- Planar Formulae and Their Uses
- One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
- A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs
- Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
- 4-chromatic projective graphs
- (2 + ?)-Coloring of planar graphs with large odd-girth
- On the algebraic theory of graph colorings
- On a conjecture of B. Grünbaum
- A Contribution to the Theory of Chromatic Polynomials
- Circular chromatic number of planar graphs of large odd girth
This page was built for publication: A Complexity Dichotomy for the Coloring of Sparse Graphs
