• Title of article

    Independence and matching number in graphs with maximum degree 4

  • Author/Authors

    Joos، نويسنده , , Felix، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2014
  • Pages
    6
  • From page
    1
  • To page
    6
  • Abstract
    We prove that 7 4 α ( G ) + β ( G ) ≥ n ( G ) and α ( G ) + 3 2 β ( G ) ≥ n ( G ) for every triangle-free graph G with maximum degree at most 4 , where α ( G ) is the independence number and β ( G ) is the matching number of G , respectively. These results are sharp for a graph on 13 vertices. Furthermore we show χ ( G ) ≤ 7 4 ω ( G ) for { 3 K 1 , K 1 ∪ K 5 } -free graphs, where χ ( G ) is the chromatic number and ω ( G ) is the clique number of G , respectively.
  • Keywords
    ? -binding function , independence number , matching number
  • Journal title
    Discrete Mathematics
  • Serial Year
    2014
  • Journal title
    Discrete Mathematics
  • Record number

    1600619