A Complexity Dichotomy for the Coloring of Sparse Graphs

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

zbMATH Keywords

complexityhomomorphismsparse graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph minors (05C83)

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