- Tytuł:
- Almost Injective Colorings
- Autorzy:
-
Goddard, Wayne
Melville, Robert
Xu, Honghai - Powiązania:
- https://bibliotekanauki.pl/articles/31343577.pdf
- Data publikacji:
- 2019-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
coloring
injective
closed neighborhood
domatic - Opis:
- We define an almost-injective coloring as a coloring of the vertices of a graph such that every closed neighborhood has exactly one duplicate. That is, every vertex has either exactly one neighbor with the same color as it, or exactly two neighbors of the same color. We present results with regards to the existence of such a coloring and also the maximum (minimum) number of colors for various graph classes such as complete k-partite graphs, trees, and Cartesian product graphs. In particular, we give a characterization of trees that have an almost-injective coloring. For such trees, we show that the minimum number of colors equals the maximum degree, and we also provide a polynomial-time algorithm for computing the maximum number of colors, even though these questions are NP-hard for general graphs.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2019, 39, 1; 225-239
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł