The multiset chromatic number of a graph.
| Další autoři: |
Chartrand, Gary, 1936-
Zhang, Ping, 1957-
|
|---|---|
| Jazyk: | angličtina |
| Předmět: | |
| Druh dokumentu: | Non-fiction |
| Abstrakt: | Abstract: A vertex coloring of a graph $G$ is a multiset coloring if the multisets of colors of the neighbors of every two adjacent vertices are different. The minimum $k$ for which $G$ has a multiset $k$-coloring is the multiset chromatic number $\chi_m(G)$ of $G$. For every graph $G$, $\chi_m(G)$ is bounded above by its chromatic number $\chi(G)$. The multiset chromatic number is determined for every complete multipartite graph as well as for cycles and their squares, cubes, and fourth powers. It is conjectured that for each $k\ge3$, there exist sufficiently large integers $n$ such that $\chi_m(C_n^k)= 3$. It is determined for which pairs $k, n$ of integers with $1\le k\le n$ and $n\ge3$, there exists a connected graph $G$ of order $n$ with $\chi_m(G)= k$. For $k= n-2$, all such graphs $G$ are determined. |
| Databáze: | Katalog Knihovny AV ČR |
| Externí odkaz: |
|