Maximizing and minimizing the number of generalized colorings of trees

被引：0
|
作者：
Engbers, John [1 ]
Stocker, Christopher [1 ]
机构：
[1] Marquette Univ, Dept Math Stat & Comp Sci, Milwaukee, WI 53201 USA
来源：
DISCRETE MATHEMATICS | 2019年 / 342卷 / 04期
关键词：
Vertex coloring; Extremal enumeration; Tree; Conflict-free coloring; UNIQUE-MAXIMUM; SETS;
D O I：
10.1016/j.disc.2018.12.015
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
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. (C) 2018 Elsevier B.V. All rights reserved.
引用
收藏
页码：1048 / 1055
页数：8
相关论文
共 50 条
  • [1] Minimizing the algebraic connectivity of trees with given matching number
    Li, Wei
    Chang, An
    UTILITAS MATHEMATICA, 2015, 97 : 355 - 365
  • [2] Trees with Given Diameter Minimizing the Augmented Zagreb Index and Maximizing the ABC Index
    Huang Yu-fei
    CommunicationsinMathematicalResearch, 2017, 33 (01) : 8 - 18
  • [3] Nonrepetitive colorings of trees
    Bresar, B.
    Grytczuk, J.
    Klavzar, S.
    Niwczyk, S.
    Peterin, I.
    DISCRETE MATHEMATICS, 2007, 307 (02) : 163 - 172
  • [4] Cost total colorings of trees
    Isobe, S
    Zhou, X
    Nishizeki, T
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2004, E87D (02) : 337 - 342
  • [5] Maximizing H-Colorings of a Regular Graph
    Galvin, David
    JOURNAL OF GRAPH THEORY, 2013, 73 (01) : 66 - 84
  • [6] LOCALLY BOUNDED k-COLORINGS OF TREES
    Bentz, C.
    Picouleau, C.
    RAIRO-OPERATIONS RESEARCH, 2009, 43 (01) : 27 - 33
  • [7] The maximum number of maximum generalized 4-independent sets in trees
    Li, Pingshan
    Xu, Min
    JOURNAL OF GRAPH THEORY, 2024, 107 (02) : 359 - 380
  • [8] The number of edge colorings with small independence number and no monochromatic H
    Hu, Xinyu
    Lin, Qizhong
    Nie, Jiaxi
    ELECTRONIC JOURNAL OF COMBINATORICS, 2025, 32 (01)
  • [9] On twin edge colorings in m-ary trees
    Tolentino, Jayson
    Marcelo, Reginaldo
    Tolentino, Mark Anthony
    ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS, 2022, 10 (01) : 131 - 149
  • [10] The Number of Colorings of the Middle Layers of the Hamming Cube
    Li, Lina
    Mckinley, Gweneth
    Park, Jinyoung
    COMBINATORICA, 2025, 45 (01)
12345