Polynomial graph-colorings
From MaRDI portal
Publication:1183345
DOI10.1016/0166-218X(92)90294-KzbMath0761.05040WikidataQ54309664 ScholiaQ54309664MaRDI QIDQ1183345
Wolfgang Gutjahr, Gerhard J. Woeginger, Ermo Welzl
Publication date: 28 June 1992
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Trees (05C05) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)
Related Items
A general approach to avoiding two by two submatrices ⋮ Graph homomorphisms with infinite targets ⋮ Homomorphisms to oriented paths ⋮ Dichotomies for classes of homomorphism problems involving unary functions ⋮ Permuting matrices to avoid forbidden submatrices ⋮ Digraph matrix partitions and trigraph homomorphisms ⋮ Algorithms for partition of some class of graphs under compaction and vertex-compaction ⋮ Complexity of tree homomorphisms ⋮ List homomorphisms to reflexive graphs ⋮ The Complexity of Approximately Counting Tree Homomorphisms ⋮ On the complexity of \(\mathbb{H}\)-coloring for special oriented trees ⋮ The smallest hard trees ⋮ Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms ⋮ On digraph coloring problems and treewidth duality ⋮ A dichotomy for minimum cost graph homomorphisms ⋮ Unnamed Item ⋮ Min-Orderable Digraphs ⋮ Colouring, constraint satisfaction, and complexity ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ Path homomorphisms ⋮ Minimum cost homomorphisms to semicomplete multipartite digraphs ⋮ On the complexity of colouring by superdigraphs of bipartite graphs ⋮ Learning logic programs with structured background knowledge ⋮ Minimum cost and list homomorphisms to semicomplete digraphs ⋮ The complexity of colouring by locally semicomplete digraphs ⋮ The \(C_{k}\)-extended graft construction ⋮ Unnamed Item ⋮ CSP dichotomy for special triads ⋮ Adjusted Interval Digraphs ⋮ Hereditarily hard \(H\)-colouring problems ⋮ CSP DICHOTOMY FOR SPECIAL POLYADS ⋮ Homomorphisms to oriented cycles ⋮ An efficient algorithm for a class of constraint satisfaction problems
Cites Work
