Square-free graphs are multiplicative
| Autor: | Marcin Wrochna |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Conjecture
Homotopy 05C60 (Primary) 05C15 55U10 (Secondary) 010102 general mathematics Multiplicative function 0102 computer and information sciences Square-free integer 01 natural sciences Theoretical Computer Science Hedetniemi's conjecture Combinatorics Computational Theory and Mathematics 010201 computation theory & mathematics FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Homomorphism Graph homomorphism Combinatorics (math.CO) 0101 mathematics Graph product Mathematics |
| Zdroj: | Journal of Combinatorial Theory, Series B. 122:479-507 |
| ISSN: | 0095-8956 |
| DOI: | 10.1016/j.jctb.2016.07.007 |
| Popis: | A graph K is square-free if it contains no four-cycle as a subgraph. A graph K is multiplicative if GxH -> K implies G -> K or H -> K, for all graphs G,H. Here GxH is the tensor (or categorical) graph product and G -> K denotes the existence of a graph homomorphism from G to K. Hedetniemi's conjecture states that all cliques K_n are multiplicative. However, the only non-trivial graphs known to be multiplicative are K_3, odd cycles, and still more generally, circular cliques $K_{p/q}$ with 2 22 pages, 5 figures. Only minor changes. Accepted for publication in JCTb |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect