Antolín Camarena, O. and Csóka, Endre and Hubai, Tamás and Lippner, Gábor and Lovász, László (2016) Positive graphs. EUROPEAN JOURNAL OF COMBINATORICS, 52. pp. 290-301. ISSN 0195-6698
Text (Publisher's PDF)
1_s2.0_S0195669815001730_main_u.pdf Restricted to Repository staff only Download (430kB) | Request a copy |
||
|
Text (arXiv manuscript)
1205.6510v2.pdf Download (210kB) | Preview |
Abstract
We study ‘‘positive’’ graphs that have a nonnegative homomorphism number into every edge-weighted graph (where the edge weights 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 but one graph up to 10 nodes. © 2015 Elsevier Ltd.All rights reserved.
Item Type: | Article |
---|---|
Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
SWORD Depositor: | MTMT SWORD |
Depositing User: | MTMT SWORD |
Date Deposited: | 02 Jan 2017 23:04 |
Last Modified: | 02 Jan 2017 23:05 |
URI: | http://real.mtak.hu/id/eprint/44206 |
Actions (login required)
Edit Item |