Polynomial graph-colorings

DOI10.1007/BFB0028977zbMATH Open1492.68063OpenAlexW1539999544MaRDI QIDQ5096147FDOQ5096147

Authors: Wolfgang Gutjahr, Gerhard J. Woeginger, Emo Welzl 

Publication date: 16 August 2022

Published in: STACS 89 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bfb0028977

Recommendations

• Polynomial graph-colorings
• Duality and Polynomial Testing of Tree Homomorphisms
• The Complexity of Colouring by Semicomplete Digraphs
• scientific article; zbMATH DE number 4101217
• scientific article; zbMATH DE number 30749

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The Complexity of Colouring by Semicomplete Digraphs
• The NP-completeness column: An ongoing guide
• Title not available (Why is that?)
• On the complexity of the general coloring problem
• Colorings and interpretations: a connection between graphs and grammar forms

Cited In (12)

• Orientations and 3-colourings of graphs.
• Graph homomorphisms with infinite targets
• Graph polynomials and group coloring of graphs
• Homomorphisms to powers of digraphs
• Title not available (Why is that?)
• \(\sigma\)-polynomials and graph coloring
• The \(C_{k}\)-extended graft construction
• Polynomial instances of the packing coloring problem
• The recognition of bound quivers using edge-coloured homomorphisms
• The complexity of colouring symmetric relational systems
• Faster graph coloring in polynomial space
• Path homomorphisms, graph colorings, and Boolean matrices

This page was built for publication: Polynomial graph-colorings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096147)