4 problems

0 votes0 replies0 views
The $C_4$ -free analogue of Vizing's conjecture
The $C_4$ -free analogue of Vizing's conjecture. It holds that
Problemrefutedc4-free-graphs chromatic-number graph-coloringarXiv posted 2 days ago
0 votes0 replies0 views
Erdős's sharpness conjecture for the extremal number of the 4-cycle
Erdős's sharpness conjecture. The lower bound is sharp for every prime power $q$ , that is,
Conjectureopenc4-free-graphs extremal-graph-theoryarXiv posted 2 days ago
0 votes0 replies1 view
The $\mathcal{O}(k\log k)$ Erdős–Pósa conjecture for long holes in $C_4$ -free graphs
For each $\ell\geq 3$ , let $C_\ell$ be the cycle of length $\ell$ . A hole is an induced cycle of length at least $4$ , and a graph is $C_4$ -free if it contains no $C_4$ . Let…
Conjectureopenc4-free-graphs erdos-possa-property induced-cyclesarXiv posted 2 days ago
0 votes0 replies0 views
The linear-logarithmic Erdős–Pósa bound conjecture for long holes in $C_4$ -free graphs
Let $C_4$ denote the cycle of length $4$ . A hole is an induced cycle of length at least $4$ , and a graph is $C_4$ -free if it contains no cycle of length $4$ . For a graph $G$ and…
Conjectureopenc4-free-graphs erdos-possa-property induced-cyclesarXiv posted 2 days ago

The C4C_4C4​-free analogue of Vizing's conjecture