• Title of article

    Maximal cliques in -free graphs

  • Author/Authors

    Choudum، نويسنده , , S.A. and Karthick، نويسنده , , T.، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2010
  • Pages
    6
  • From page
    3398
  • To page
    3403
  • Abstract
    We prove a decomposition theorem for the class G of { P 2 ∪ P 3 , C 4 } -free graphs. This theorem enables us to show that (i) every graph G in G has at most n + 5 maximal cliques where n is the number of vertices in G , and (ii) for every G in G , χ ( G ) ≤ ⌈ 5 ω ( G ) 4 ⌉ , where χ ( G ) ( ω ( G ) ) is the chromatic (clique) number of G .
  • Keywords
    C 4 -free graphs , Maximal cliques , chromatic number , chordal graphs
  • Journal title
    Discrete Mathematics
  • Serial Year
    2010
  • Journal title
    Discrete Mathematics
  • Record number

    1599510