Chromatic Number, Induced Cycles, and Non-separating Cycles
- PDF / 432,560 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 94 Downloads / 231 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Chromatic Number, Induced Cycles, and Non-separating Cycles Hanbaek Lyu1 Received: 22 February 2017 / Revised: 14 April 2020 Ó Springer Japan KK, part of Springer Nature 2020
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 every 3-connected graph with average degree at least 2k for some k 2 have at least ðk 1ÞjVj þ Ck3 log3=2 k induced non-separating cycles for some explicit constant C [ 0. This improves the previous best known lower bound ðk 1ÞjVj þ 1, which follows from Tutte’s cycle space theorem. We also give a short proof of this theorem of Tutte. Keywords Chromatic number Induced cycles Hadwiger number Induced non-separating cycles Euler characteristic
Mathematics Subject Classification 05C15 05C83 05C38
1 Introduction Understanding structure of graphs is often a formidable task. But sometimes, simply counting the number of basic objects such as vertices, edges, and cycles, gives a good understanding on some structural properties of the graphs. This is best illustrated by a classic theorem of Euler, which says that the alternating sum of the number of faces, edges and vertices in a graph G determines its genus. Namely, if a graph G is obtained by a 2-cell division of an orientable surface of genus g, then & Hanbaek Lyu [email protected] 1
University of California, Los Angeles, 520 Portola Plaza, MS 6156, Los Angeles, CA 90095, USA
123
Graphs and Combinatorics
jFðGÞj jEðGÞj þ jVðGÞj ¼ 2 2g
ð1Þ
where FðGÞ is the set of all faces in G. The quantity in the left hand side is called the Euler characteristic. The notion of faces depends not only on the graph itself but also on the underlying surface on which the graph is drawn. However, it is well known that face boundaries of a 3-connected planar graphs are precisely given by its induced nonseparating cycles. Hence, it is natural to replace the set FðGÞ of all faces in the Euler characteristic by some other class of cycles CðGÞ. Parameters obtained in this way could be used to study different structural properties of graphs other than their genus. Indeed, Vince and Little [8] and Yu [9] used the parameter when CðGÞ is a cycle double cover (a collection of cycles such that each edge is contained in exactly two cycles in CðGÞ) in oder to study discrete Jordan curves. In this paper, we study two parameters when CðGÞ is the set C(G) of all induced cycles and the set F(G) of all induced non-separating cycles in G. Let vðGÞ denote the chromatic number of G. Our first main result is the following. Theorem 1 Let G ¼ ðV; EÞ be a connected graph and let C(G) denote the set o
Data Loading...
