Title of article :
Coloring the hypergraph of maximal cliques of a graph with no long path
Author/Authors :
Sylvain Gravier and Julien Moncel، نويسنده , , Chinh T. Hoàng، نويسنده , , Frédéric Maffray، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2003
Pages :
6
From page :
285
To page :
290
Abstract :
We consider the problem of coloring the vertices of a graph so that no maximal clique of size at least two is monocolored. We solve the following question: Given a fixed graph F, does there exist an integer f(F) such that the hypergraph of maximal cliques of any F-free graph can be f(F)-colored? We show that the answer is positive if and only if all components of F are paths. In that case we give an estimate of f(F), and the proof contains a polynomial time algorithm to find such a coloring.
Keywords :
Graphs , Coloring , Maximal cliques
Journal title :
Discrete Mathematics
Serial Year :
2003
Journal title :
Discrete Mathematics
Record number :
948678
Link To Document :
بازگشت