Positive graphs
From MaRDI portal
Publication:5899554
DOI10.1016/J.EJC.2015.07.007zbMATH Open1327.05236arXiv1205.6510OpenAlexW2914490195MaRDI QIDQ5899554FDOQ5899554
Omar Antolín Camarena, Gabor Lippner, Endre Csóka, László Lovász, Tamás Hubai
Publication date: 11 December 2015
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Abstract: We study "positive" graphs that have a nonnegative homomorphism number into every edge-weighted graph (where the edgeweights may be negative). We conjecture that all positive graphs can be obtained by taking two copies of an arbitrary simple graph and gluing them together along an independent set of nodes. We prove the conjecture for various classes of graphs including all trees. We prove a number of properties of positive graphs, including the fact that they have a homomorphic image which has at least half the original number of nodes but in which every edge has an even number of pre-images. The results, combined with a computer program, imply that the conjecture is true for all graphs up to 9 nodes.
Full work available at URL: https://arxiv.org/abs/1205.6510
Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Signed and weighted graphs (05C22)
Cites Work
Cited In (10)
- Graphs with positive spectrum
- On graph norms for complex‐valued functions
- Finite reflection groups and graph norms
- On positive hypergraphs
- Impartial digraphs
- Positive graphs
- Positive Fork Graph Calculus
- Extended commonality of paths and cycles via Schur convexity
- Locally common graphs
- Domination inequalities and dominating graphs
This page was built for publication: Positive graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5899554)
