• Title of article

    Independence, irredundance, degrees and chromatic number in graphs

  • Author/Authors

    G?bor Bacs?، نويسنده , , Odile Favaron، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2002
  • Pages
    6
  • From page
    257
  • To page
    262
  • Abstract
    Let β(G) and IR(G) denote the independence number and the upper irredundance number of a graph G. We prove that in any graph of order n, minimum degree δ and maximum degree Δ≠0, IR(G)⩽n/(1+δ/Δ) and IR(G)−β(G)⩽((Δ−2)/2Δ)n. The two bounds are attained by arbitrarily large graphs. The second one proves a conjecture by Rautenbach related to the case Δ=3. When the chromatic number χ of G is less than Δ, it can be improved to IR(G)−β(G)⩽((χ−2)/2χ)n in any non-empty graph of order n⩾2.
  • Keywords
    Chromatic number , Independence , Irredundance , Graph
  • Journal title
    Discrete Mathematics
  • Serial Year
    2002
  • Journal title
    Discrete Mathematics
  • Record number

    949411