Article in press
Authors:
Title:
Bounds on coloring trees without rainbow paths
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2024-12-21 , Revised: 2025-03-10 , Accepted: 2025-03-11 , Available online: 2025-04-02 , https://doi.org/10.7151/dmgt.2582
Abstract:
For a graph with colored vertices, a rainbow subgraph is one where all vertices
have different colors. For graph $G$, let $\mathit{c}_k(G)$ denote the maximum number
of different colors in a coloring without a rainbow path on $k$ vertices, and
${\mathit{cp}}_k(G)$ the maximum number of colors if the coloring is required to be
proper. The parameter ${\mathit{c}}_3$ has been studied by multiple authors. We
investigate these parameters for trees and $k \ge 4$. We first calculate them
when $G$ is a path, and determine when the optimal coloring is unique. Then for
trees $T$ of order $n$, we show that the minimum value of $\mathit{c}_4(T)$ and
${\mathit{cp}}_4(T)$ is $(n+2)/2$, and the trees with the minimum value of ${\mathit{cp}}_{4}T)$
are the coronas. Further, the minimum value of $\mathit{c}_5(T)$ and ${\mathit{cp}}_{5}(T)$ is
$(n+3)/2$, and the trees with the minimum value of either parameter are octopuses.
Keywords:
no-rainbow, path, tree, corona
References:
- M. Axenovich and R. Martin, Avoiding rainbow induced subgraphs in vertex-colorings, Electron. J. Combin. 15(1) (2008) #R12.
- Cs. Bujtás and Zs. Tuza, Maximum number of colors: $C$-coloring and related problems, J. Geom. 101 (2011) 83–97.
https://doi.org/10.1007/s00022-011-0082-2 - Cs. Bujtás, E. Sampathkumar, Zs. Tuza, C. Dominic and L. Pushpalatha, Vertex coloring without large polychromatic stars, Discrete Math. 312 (2012) 2102–2108.
https://doi.org/10.1016/j.disc.2011.04.013 - Cs. Bujtás, E. Sampathkumar, Zs. Tuza, M.S. Subramanya and C. Dominic, $3$-consecutive $C$-colorings of graphs, Discuss. Math. Graph Theory 30 (2010) 393–405.
https://doi.org/10.7151/dmgt.1502 - E. Bulgaru and V.I. Voloshin, Mixed interval hypergraphs, Discrete Appl. Math. 77 (1997) 29–41.
https://doi.org/10.1016/S0166-218X(97)89209-8 - J.D. Chandler, W.J. Desormeaux, T.W. Haynes and S.T. Hedetniemi, Neighborhood-restricted $[\le 2]$-achromatic colorings, Discrete Appl. Math. 207 (2016) 39–44.
https://doi.org/10.1016/j.dam.2016.02.023 - W. Goddard and H. Xu, Vertex colorings without rainbow subgraphs, Discuss. Math. Graph Theory 36 (2016) 989–1005.
https://doi.org/10.7151/dmgt.1896 - W. Goddard and H. Xu, Vertex colorings without rainbow or monochromatic subgraphs, J. Combin. Math. Combin. Comput. 102 (2017) 109–122.
- W. Goddard, K. Wash and H. Xu, WORM colorings, Discuss. Math. Graph Theory 35 (2015) 571–584.
https://doi.org/10.7151/dmgt.1814 - V. Voloshin, On the upper chromatic number of a hypergraph, Australas. J. Combin. 11 (1995) 25–45.
Close