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
Link To Document