Article contents
ON PROBLEMS OF
$\boldsymbol{\mathcal{CF}}$-CONNECTED GRAPHS FOR
$\boldsymbol{K}_{\boldsymbol{m,n}}$
Published online by Cambridge University Press: 01 December 2020
Abstract
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 $
.
MSC classification
- Type
- Research Article
- Information
- Bulletin of the Australian Mathematical Society , Volume 104 , Issue 2 , October 2021 , pp. 203 - 210
- Copyright
- © 2020 Australian Mathematical Publishing Association Inc.
References
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20210906001802031-0934:S000497272000129X:S000497272000129X_inline13.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20210906001802031-0934:S000497272000129X:S000497272000129X_inline14.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20210906001802031-0934:S000497272000129X:S000497272000129X_inline15.png?pub-status=live)
- 1
- Cited by