Square-free graphs are multiplicative

详细信息    查看全文

• 作者：Marcin Wrochna ^{m.wrochna@mimuw.edu.pl}
• 关键词：Square-free ; Four-cycle-free ; Homomorphism ; Hedetniemi's conjecture ; Homotopy ; Multiplicativity ; Box complex
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：122
• 期：Complete
• 页码：479-507
• 全文大小：923 K
• 卷排序：122

文摘

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)v0v1,v1v2,v2v3,v3v0∈E(K), then v0=v2v0=v2 or v1=v3v1=v3). A graph K is multiplicative   if G×H→KG×H→K implies G→KG→K or H→KH→K, for all graphs G, H  . Here G×HG×H is the tensor (or categorical) graph product and G→KG→K denotes the existence of a graph homomorphism from G to K  . Hedetniemi's conjecture, which states that χ(G×H)=min⁡(χ(G),χ(H))χ(G×H)=min⁡(χ(G),χ(H)), is equivalent to the statement that all cliques KnKn are multiplicative. However, the only non-trivial graphs known to be multiplicative are K3K3, odd cycles, and still more generally, circular cliques Kp/qKp/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.