Chromatic number, induced cycles, and non-separating cycles

DOI10.1007/S00373-020-02187-4MaRDI QIDQ2227971zbMATH OpenOpenAlexFDO

Authors Hanbaek Lyu

Publication date 16 February 2021

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1211.0627

zbMATH Keywords

chromatic numberEuler characteristicHadwiger numberinduced cyclesinduced non-separating cycles

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Graph minors (05C83)

Abstract: 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 $kge2$ have at least $(k-1)|V|+C{k}^{3}lo{g}^{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.

Recommendations

• Nonseparating cycles avoiding specific vertices
• On the connection between the chromatic number of a graph and the number of cycles covering a vertex or an edge
• scientific article; zbMATH DE number 568792
• Induced cycles and chromatic number
• Nonseparating Induced Cycles Consisting of Contractible Edges in k-Connected Graphs

Cites work

• Contractible non-edges in \(3\)-connected graphs
• Discrete Jordan curve theorems
• How to Draw a Graph
• scientific article; zbMATH DE number 3166039 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• Lower bound of the Hadwiger number of graphs by their average degree
• Non-separating cycles and discrete Jordan curves
• Planarity and duality of finite and infinite graphs

Cited in

(4)

• A note on chromatic number and induced odd cycles
• Dichromatic number and forced subdivisions
• Chromatic number, independence ratio, and crossing number
• Uncountable dichromatic number without short directed cycles

This page was built for publication: Chromatic number, induced cycles, and non-separating cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2227971)