Injective coloring of product graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911906758918144 |
|---|---|
| author | Samadi, Babak Soltankhah, Nasrin Yero, Ismael G. |
| author_facet | Samadi, Babak Soltankhah, Nasrin Yero, Ismael G. |
| contents | The problem of injective coloring in graphs can be revisited through two different approaches: coloring the two-step graphs and vertex partitioning of graphs into open packing sets, each of which is equivalent to the injective coloring problem itself. Taking these facts into account, we observe that the injective coloring lies between graph coloring and domination theory.
We make use of these three points of view in this paper so as to investigate the injective coloring of some well-known graph products. We bound the injective chromatic number of direct and lexicographic product graphs from below and above. In particular, we completely determine this parameter for the direct product of two cycles. We also give a closed formula for the corona product of two graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_01488 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Injective coloring of product graphs Samadi, Babak Soltankhah, Nasrin Yero, Ismael G. Combinatorics 05C15, 05C69, 05C76 The problem of injective coloring in graphs can be revisited through two different approaches: coloring the two-step graphs and vertex partitioning of graphs into open packing sets, each of which is equivalent to the injective coloring problem itself. Taking these facts into account, we observe that the injective coloring lies between graph coloring and domination theory. We make use of these three points of view in this paper so as to investigate the injective coloring of some well-known graph products. We bound the injective chromatic number of direct and lexicographic product graphs from below and above. In particular, we completely determine this parameter for the direct product of two cycles. We also give a closed formula for the corona product of two graphs. |
| title | Injective coloring of product graphs |
| topic | Combinatorics 05C15, 05C69, 05C76 |
| url | https://arxiv.org/abs/2306.01488 |