Achromatic number of fragmentable graphs

    Research output: Contribution to journalArticle

    4 Citations (Scopus)

    Abstract

    A complete coloring of a simple graph G is a proper vertex coloring such that each pair of colors appears together on at least one edge. The achromatic number psi(G) is the greatest number of colors in such a coloring. We say a class of graphs is fragmentable if for any positive epsilon, there is a constant C such that any graph in the class can be broken into pieces of size at most C by removing a proportion at most epsilon of the vertices. Examples include planar graphs and grids of fixed dimension. Determining the achromatic number of a graph is NP-complete in general, even for trees, and the achromatic number is known precisely for only very restricted classes of graphs. We extend these classes very considerably, by giving, for graphs in any class which is fragmentable, triangle-free, and of bounded degree, a necessary and sufficient condition for a sufficiently large graph to have a complete coloring with a given number of colors. For the same classes, this gives a tight lower bound for the achromatic number of sufficiently large graphs, and shows that the achromatic number can be determined in polynomial time. As examples, we give exact values of the achromatic number for several graph families. (C) 2009 Wiley Periodicals, Inc. J Graph Theory 65: 94-114, 2010

    Original languageEnglish
    Pages (from-to)94-114
    Number of pages21
    JournalJournal of Graph Theory
    Volume65
    Issue number2
    DOIs
    Publication statusPublished - Oct 2010

    Keywords

    • achromatic number
    • detachment
    • fragmentable graph
    • APPROXIMATION ALGORITHMS
    • UNION

    Cite this