A Complexity Dichotomy for the Coloring of Sparse Graphs
From MaRDI portal
Publication:4920652
DOI10.1002/JGT.21659zbMATH Open1264.05049OpenAlexW1548527711MaRDI QIDQ4920652FDOQ4920652
Authors: L. Esperet, Mickaël Montassier, Pascal Ochem, Alexandre Pinlou 
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
Recommendations
- On coloring of sparse graphs
- scientific article; zbMATH DE number 3876617
- A GRASP for coloring sparse graphs
- The complexity of colouring problems on dense graphs
- \((k,1)\)-coloring of sparse graphs
- Colouring graphs with sparse neighbourhoods: bounds and applications
- The complexity of some graph colouring problems
- scientific article; zbMATH DE number 1670678
- The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
- On sparse graphs with given colorings and homomorphisms.
Cites Work
- A Contribution to the Theory of Chromatic Polynomials
- Acyclic Colourings of Planar Graphs with Large Girth
- Planar Formulae and Their Uses
- A simplified NP-complete satisfiability problem
- Some simplified NP-complete graph problems
- On the algebraic theory of graph colorings
- Homomorphisms from sparse graphs with large girth.
- One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
- 4-chromatic projective graphs
- On a conjecture of B. Grünbaum
- Planar graphs without cycles of length from 4 to 7 are 3-colorable
- A note on the three color problem
- Title not available (Why is that?)
- Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
- Title not available (Why is that?)
- Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion)
- 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\)
- Near-proper vertex 2-colorings of sparse graphs
- Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1
- On the complexity of \(H\)-colouring planar graphs
- (2 + ?)-Coloring of planar graphs with large odd-girth
- Sachs' linkless embedding conjecture
- A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs
- High-girth graphs avoiding a minor are nearly bipartite
- Acyclic 3-choosability of planar graphs with no cycles of length from 4 to 11
- On the invariance of Colin de Verdière's graph parameter under clique sums
- Circular chromatic number of planar graphs of large odd girth
- Some counterexamples associated with the three-color problem
- A minor-monotone graph parameter based on oriented matroids
- Title not available (Why is that?)
Cited In (23)
- Average-case complexity of backtrack search for coloring sparse random graphs
- Improper coloring of sparse graphs with a given girth. I: \((0,1)\)-colorings of triangle-free graphs
- \(k\)-forested coloring of sparse graphs
- Near-colorings: non-colorable graphs and NP-completeness
- Vertex partitions of \((C_3, C_4, C_6)\)-free planar graphs
- On 1-improper 2-coloring of sparse graphs
- On 2-defective DP-colorings of sparse graphs
- Characterization of Cycle Obstruction Sets for Improper Coloring Planar Graphs
- Improper coloring of sparse graphs with a given girth. II: Constructions
- Complexity dichotomy for oriented homomorphism of planar graphs with large girth
- NP-Completeness of Spreading Colored Points
- Fine-grained complexity for sparse graphs
- A GRASP for coloring sparse graphs
- Sparse critical graphs for defective DP-colorings
- Modulo orientations and matchings in graphs
- Complexity of planar signed graph homomorphisms to cycles
- On sparse graphs with given colorings and homomorphisms.
- (1,k)-Coloring of Graphs with Girth at Least Five on a Surface
- Vertex Partitions into an Independent Set and a Forest with Each Component Small
- Defective DP-colorings of sparse multigraphs
- Defective DP-colorings of sparse simple graphs
- Title not available (Why is that?)
- Partitioning sparse graphs into an independent set and a graph with bounded size components
This page was built for publication: A Complexity Dichotomy for the Coloring of Sparse Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4920652)
