• 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