کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777666 | 1632971 | 2017 | 29 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Square-free graphs are multiplicative
ترجمه فارسی عنوان
نمودارهای بدون انحنای چندگانه هستند
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
A graph K is square-free if it contains no four-cycle as a subgraph (i.e., for every quadruple of vertices, if v0v1,v1v2,v2v3,v3v0âE(K), then v0=v2 or v1=v3). A graph K is multiplicative if GÃHâK implies GâK or HâK, for all graphs G, H. Here GÃH is the tensor (or categorical) graph product and GâK denotes the existence of a graph homomorphism from G to K. Hedetniemi's conjecture, which states that Ï(GÃH)=minâ¡(Ï(G),Ï(H)), is equivalent to the statement that all cliques Kn are multiplicative. However, the only non-trivial graphs known to be multiplicative are K3, odd cycles, and still more generally, circular cliques Kp/q with 2â¤pq<4. We make no progress for cliques, but show that all square-free graphs are multiplicative. In particular, this gives the first multiplicative graphs of chromatic number higher than 4. Generalizing, in terms of the box complex, the topological insight behind existing proofs for odd cycles, we also give a different proof for circular cliques with 2â¤pq<4.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 122, January 2017, Pages 479-507
Journal: Journal of Combinatorial Theory, Series B - Volume 122, January 2017, Pages 479-507
نویسندگان
Marcin Wrochna,