Achromatic number versus pseudoachromatic number

A counterexample to a conjecture of Hedetniemi

    Research output: Contribution to journalArticle

    8 Citations (Scopus)

    Abstract

    The pseudoachromatic number of a graph is the largest number of colours in a (not necessarily proper) vertex colouring of the graph such that every pair of distinct colours appears on the endpoints of some edge. The achromatic number is largest number of colours which can be used if the colouring must also be proper. Hedetniemi (http://cyclone.cs.clemson.edu/~hedet/coloring.html) conjectured that these two parameters are equal for all trees. We disprove this conjecture by giving an infinite family of trees for which the pseudoachromatic number strictly exceeds the achromatic number.
    Original languageEnglish
    Pages (from-to)271-274
    Number of pages4
    JournalDiscrete Mathematics
    Volume219
    Issue number1-3
    DOIs
    Publication statusPublished - 28 May 2000

    Fingerprint

    Achromatic number
    Coloring
    Counterexample
    Color
    Colouring
    Vertex Coloring
    Disprove
    Graph in graph theory
    Two Parameters
    Exceed
    Strictly
    Distinct

    Cite this

    @article{0445781a1c654760be483ddd0453c0a7,
    title = "Achromatic number versus pseudoachromatic number: A counterexample to a conjecture of Hedetniemi",
    abstract = "The pseudoachromatic number of a graph is the largest number of colours in a (not necessarily proper) vertex colouring of the graph such that every pair of distinct colours appears on the endpoints of some edge. The achromatic number is largest number of colours which can be used if the colouring must also be proper. Hedetniemi (http://cyclone.cs.clemson.edu/~hedet/coloring.html) conjectured that these two parameters are equal for all trees. We disprove this conjecture by giving an infinite family of trees for which the pseudoachromatic number strictly exceeds the achromatic number.",
    author = "Edwards, {Keith J.}",
    note = "Copyright 2004 Elsevier Science B.V., Amsterdam. All rights reserved.",
    year = "2000",
    month = "5",
    day = "28",
    doi = "10.1016/S0012-365X(00)00025-X",
    language = "English",
    volume = "219",
    pages = "271--274",
    journal = "Discrete Mathematics",
    issn = "0012-365X",
    publisher = "Elsevier",
    number = "1-3",

    }

    Achromatic number versus pseudoachromatic number : A counterexample to a conjecture of Hedetniemi. / Edwards, Keith J.

    In: Discrete Mathematics, Vol. 219, No. 1-3, 28.05.2000, p. 271-274.

    Research output: Contribution to journalArticle

    TY - JOUR

    T1 - Achromatic number versus pseudoachromatic number

    T2 - A counterexample to a conjecture of Hedetniemi

    AU - Edwards, Keith J.

    N1 - Copyright 2004 Elsevier Science B.V., Amsterdam. All rights reserved.

    PY - 2000/5/28

    Y1 - 2000/5/28

    N2 - The pseudoachromatic number of a graph is the largest number of colours in a (not necessarily proper) vertex colouring of the graph such that every pair of distinct colours appears on the endpoints of some edge. The achromatic number is largest number of colours which can be used if the colouring must also be proper. Hedetniemi (http://cyclone.cs.clemson.edu/~hedet/coloring.html) conjectured that these two parameters are equal for all trees. We disprove this conjecture by giving an infinite family of trees for which the pseudoachromatic number strictly exceeds the achromatic number.

    AB - The pseudoachromatic number of a graph is the largest number of colours in a (not necessarily proper) vertex colouring of the graph such that every pair of distinct colours appears on the endpoints of some edge. The achromatic number is largest number of colours which can be used if the colouring must also be proper. Hedetniemi (http://cyclone.cs.clemson.edu/~hedet/coloring.html) conjectured that these two parameters are equal for all trees. We disprove this conjecture by giving an infinite family of trees for which the pseudoachromatic number strictly exceeds the achromatic number.

    UR - http://www.scopus.com/inward/record.url?scp=0347646985&partnerID=8YFLogxK

    U2 - 10.1016/S0012-365X(00)00025-X

    DO - 10.1016/S0012-365X(00)00025-X

    M3 - Article

    VL - 219

    SP - 271

    EP - 274

    JO - Discrete Mathematics

    JF - Discrete Mathematics

    SN - 0012-365X

    IS - 1-3

    ER -