The complexity of tropical graph homomorphisms
From MaRDI portal
Publication:2012054
DOI10.1016/j.dam.2017.04.027zbMath1367.05141arXiv1607.04777MaRDI QIDQ2012054
Reza Naserasr, Yannis Manoussakis, Sylvain Legay, Florent Foucaud, Ararat Harutyunyan, Pavol Hell
Publication date: 27 July 2017
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1607.04777
05C15: Coloring of graphs and hypergraphs
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Related Items
Tropical paths in vertex-colored graphs, Oriented, 2-edge-colored, and 2-vertex-colored homomorphisms, The complexity of tropical graph homomorphisms, Complexity of correspondence \(H\)-colourings
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The effect of two cycles on the complexity of colourings by directed graphs
- On the complexity of H-coloring
- List homomorphisms to reflexive graphs
- Characterization problems for graphs, partially ordered sets, lattices, and families of sets
- Homomorphisms of edge-colored graphs and Coxeter groups
- The complexity of colouring symmetric relational systems
- Hereditarily hard \(H\)-colouring problems
- Complexity of tree homomorphisms
- List homomorphisms and circular arc graphs
- The complexity of tropical graph homomorphisms
- The complexity of signed graph and edge-coloured graph homomorphisms
- Classification of Homomorphisms to Oriented Cycles and of k-Partite Satisfiability
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
- Boolean Difference Techniques for Time-Sequence and Common-Cause Analysis of Fault-Trees
- The Complexity of Colouring by Semicomplete Digraphs
- On the Structure of Polynomial Time Reducibility
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Bi‐arc graphs and the complexity of list homomorphisms
- Reducibility among Combinatorial Problems
- The complexity of satisfiability problems
- Full Constraint Satisfaction Problems
- The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
