• Title of article

    The independence number in graphs of maximum degree three

  • Author/Authors

    Jochen Harant، نويسنده , , Michael A. Henning، نويسنده , , Dieter Rautenbach، نويسنده , , Ingo Schiermeyer، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2008
  • Pages
    5
  • From page
    5829
  • To page
    5833
  • Abstract
    We prove that a image-free graph image of order image, size image and maximum degree at most three has an independent set of cardinality at least image, where image counts the number of components of image whose blocks are each either isomorphic to one of four specific graphs or edges between two of these four specific graphs and image is the maximum number of vertex-disjoint triangles in image. Our result generalizes a bound due to Heckman and Thomas [C.C. Heckman, R. Thomas, A new proof of the independence ratio of triangle-free cubic graphs, Discrete Math. 233 (2001) 233–237].
  • Keywords
    Triangle , Cubic graph , Independence
  • Journal title
    Discrete Mathematics
  • Serial Year
    2008
  • Journal title
    Discrete Mathematics
  • Record number

    947204