- Tytuł:
- Recognizable colorings of graphs
- Autorzy:
-
Chartrand, Gary
Lesniak, Linda
VanderJagt, Donald
Zhang, Ping - Powiązania:
- https://bibliotekanauki.pl/articles/743507.pdf
- Data publikacji:
- 2008
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
recognizable coloring
recognition number - Opis:
- Let G be a connected graph and let c:V(G) → {1,2,...,k} be a coloring of the vertices of G for some positive integer k (where adjacent vertices may be colored the same). The color code of a vertex v of G (with respect to c) is the ordered (k+1)-tuple code(v) = (a₀,a₁,...,aₖ) where a₀ is the color assigned to v and for 1 ≤ i ≤ k, $a_i$ is the number of vertices adjacent to v that are colored i. The coloring c is called recognizable if distinct vertices have distinct color codes and the recognition number rn(G) of G is the minimum positive integer k for which G has a recognizable k-coloring. Recognition numbers of complete multipartite graphs are determined and characterizations of connected graphs of order n having recognition numbers n or n-1 are established. It is shown that for each pair k,n of integers with 2 ≤ k ≤ n, there exists a connected graph of order n having recognition number k. Recognition numbers of cycles, paths, and trees are investigated.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2008, 28, 1; 35-57
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł