Bounded vertex coloring of trees (Q5937457)

From MaRDI portal
Revision as of 10:00, 30 July 2024 by Openalex240730090724 (talk | contribs) (Set OpenAlex properties.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article; zbMATH DE number 1619293
Language Label Description Also known as
English
Bounded vertex coloring of trees
scientific article; zbMATH DE number 1619293

    Statements

    Bounded vertex coloring of trees (English)
    0 references
    0 references
    0 references
    17 February 2002
    0 references
    The \(k\)-bounded chromatic number, \(\chi _{k}(G),\) of a graph \(G\) is the minimum number of colors required to color the vertices of \(G\) such that no two vertices receive the same color and each color is assigned to at most \(k\) vertices. It is shown that \(\chi _{k}(T)\leq \left\lceil n/k\right\rceil +1\) for every tree \(T\). The authors state that they characterize the trees that cannot be colored with the smallest possible number of colors. What they actually do is to characterize the trees with \(k\)-bounded chromatic number \(\left\lceil n/k\right\rceil +1.\)
    0 references
    bounded coloring
    0 references
    bounded chromatic number
    0 references
    trees
    0 references

    Identifiers