Article ID Journal Published Year Pages File Type
4648820 Discrete Mathematics 2011 8 Pages PDF
Abstract

The even-girth of any graph GG is the smallest length of any even cycle in GG. For any two integers t,kt,k with 0≤t≤k−20≤t≤k−2, we denote the maximum number of cycles of length kk such that each pair of cycles intersect in exactly a unique path of length tt by bt,k(G)bt,k(G). This parameter is called the (t,k)(t,k)-booksize of GG. In this paper we obtain some upper bounds for the chromatic and coloring numbers of graphs in terms of even-girth and booksize. We also prove some bounds for graphs which contain no cycle of length tt where tt is a small and fixed even integer.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,