Maximizing and minimizing the number of generalized colorings of trees

We classify the trees on n vertices with the maximum and the minimum number of certain generalized colorings, including conflict-free, odd, non-monochromatic, star, and star rainbow vertex colorings. We also extend a result of Cutler and Radcliffe on the maximum and minimum number of existence homom...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2019-04, Vol.342 (4), p.1048-1055
Main Authors: Engbers, John, Stocker, Christopher
Format: Article
Language:English
Subjects:
Conflict-free coloring
Extremal enumeration
Tree
Vertex coloring
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We classify the trees on n vertices with the maximum and the minimum number of certain generalized colorings, including conflict-free, odd, non-monochromatic, star, and star rainbow vertex colorings. We also extend a result of Cutler and Radcliffe on the maximum and minimum number of existence homomorphisms from a tree to a completely looped graph on q vertices.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2018.12.015