ON PROBLEMS OF -CONNECTED GRAPHS FOR
| Autor: | Michal Staš, Juraj Valiska |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| Zdroj: | Bulletin of the Australian Mathematical Society. 104:203-210 |
| ISSN: | 1755-1633 0004-9727 |
| DOI: | 10.1017/s000497272000129x |
| Popis: | A connected graph G is $\mathcal {CF}$ -connected if there is a path between every pair of vertices with no crossing on its edges for each optimal drawing of G. We conjecture that a complete bipartite graph $K_{m,n}$ is $\mathcal {CF}$ -connected if and only if it does not contain a subgraph of $K_{3,6}$ or $K_{4,4}$ . We establish the validity of this conjecture for all complete bipartite graphs $K_{m,n}$ for any $m,n$ with $\min \{m,n\}\leq 6$ , and conditionally for $m,n\geq 7$ on the assumption of Zarankiewicz’s conjecture that $\mathrm {cr}(K_{m,n})=\big \lfloor \frac {m}{2} \big \rfloor \big \lfloor \frac {m-1}{2} \big \rfloor \big \lfloor \frac {n}{2} \big \rfloor \big \lfloor \frac {n-1}{2} \big \rfloor $ . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|