New upper bounds for the bondage number of a graph in terms of its maximum degree and Euler characteristic. The bondage number b(G) of a graph G is the smallest number of edges whose removal from G results in a graph with larger domination number. Let G be embeddable on a surface whose Euler characteristic chi is as large as possible, and assume chileq0. GagarinZverovich and Huang have recently found upper bounds of b(G) in terms of the maximum degree Delta(G) and the Euler characteristic chi(G)chi. In this paper we prove a better upper bound b(G)leqDelta(G)lfloor trfloor where t is the largest real root of the cubic equation z3  z2  (3chi  8)z  9chi  120; this upper bound is asymptotically equivalent to b(G)leqDelta(G)1lfloor sqrt43chi rfloor. We also establish further improved upper bounds for b(G) when the girth, order, or size of the graph G is large compared with its Euler characteristic chi.

Chromatic numbers of Knesertype graphs Abstract   Let    G  (  n  ,  r  ,  s  )    be a graph whose vertices are all relement subsets of an nelement set, in which two vertices are adjacent if they intersect in exactly s elements. In this paper we study chromatic numbers of    G  (  n  ,  r  ,  s  )    with    r  ,  s    being fixed constants and n tending to infinity. Using a recent result of Keevash on existence of designs we deduce an inequality    xcfx87  (  G  (  n  ,  r  ,  s  )  )  xe2xa9xbd  (  1    o  (  1  )  )    n    r  xe2x88x92  s      (  r  xe2x88x92  s  xe2x88x92  1  )  !    (  2  r  xe2x88x92  2  s  xe2x88x92  1  )  !      for    r  u003e  s    with    r  ,  s    fixed constants. This inequality gives sharp upper bounds for    r  xe2xa9xbd  2  s    1   . Also we develop an elementary approach to this problem and prove that    xcfx87  (  G  (  n  ,  4  ,  2  )  )  xe2x88xbc      n    2      6      without use of Keevashu0027s results.  Some bounds on the list chromatic number of    G  (  n  ,  r  ,  s  )    are also obtained.