ProV Logo
0
Chromatic number, induced cycles, and no...
Lyu, Hanbaek...

Free

Chromatic number, induced cycles, and non-separating cycles by Lyu, Hanbaek ( Author )
Lemonjar Open Access
Australian National University
27-07-2023
We study two parameters obtained from the Euler characteristic by replacing the number of faces with that of induced and induced non-separating cycles. By establishing monotonicity of such parameters under certain homomorphism and edge contraction, we obtain new upper bounds on the chromatic number in terms of the number of induced cycles and the Hadwiger number in terms of the number of induced non-separating cycles. As an application, we show that a 3-connected graph with average degree $k\ge 2$ have at least $(k-1)|V|+Ck^{3}\log^{3/2}k$ induced non-separating cycles for some explicit constant $C>0$. This improves the previous best lower bound $(k-1)|V|+1$, which follows from Tutte's cycle space theorem. We also give a short proof of this theorem of Tutte.
-
Article
pdf
29.34 KB
English
-
MYR 0.01
-
http://arxiv.org/abs/1211.0627
Share this eBook