Artículo
Bonomo, F.; Koch, I.; Torres, P.; Valencia-Pabon, M. "k-tuple chromatic number of the cartesian product of graphs" (2015) Electronic Notes in Discrete Mathematics. 50:243-248
Consulte la política de Acceso Abierto del editor
Abstract:
A k-tuple coloring of a graph G assigns a set of k colors to each vertex of G such that if two vertices are adjacent, the corresponding sets of colors are disjoint. The k-tuple chromatic number of G, χk(G), is the smallest t so that there is a k-tuple coloring of G using t colors. It is well known that χ(G□H)=max{χ(G), χ(H)}. In this paper, we show that there exist graphs G and H such that χk(G□H)>max{χk(G), χk(H)} for k≥2. Moreover, we also show that there exist graph families such that, for any k≥1, the k-tuple chromatic number of their cartesian product is equal to the maximum k-tuple chromatic number of its factors. © 2015 Elsevier B.V.
Registro:
| Documento: | Artículo |
| Título: | k-tuple chromatic number of the cartesian product of graphs |
| Autor: | Bonomo, F.; Koch, I.; Torres, P.; Valencia-Pabon, M. |
| Filiación: | CONICET and DC, FCEN, Universidad de Buenos Aires, Argentina Instituto de Ciencias, Universidad Nacional de General Sarmiento, Argentina Universidad Nacional de Rosario and CONICET, Argentina Université Paris-13, Sorbonne Paris Cité LIPN, CNRS UMR7030, Villetaneuse, France Délégation at the INRIA Nancy - Grand Est, France |
| Palabras clave: | Cartesian product of graphs; Cayley graphs; Hom-idempotent graphs; k-tuple colorings; Kneser graphs |
| Año: | 2015 |
| Volumen: | 50 |
| Página de inicio: | 243 |
| Página de fin: | 248 |
| DOI: | http://dx.doi.org/10.1016/j.endm.2015.07.041 |
| Título revista: | Electronic Notes in Discrete Mathematics |
| Título revista abreviado: | Electron. Notes Discrete Math. |
| ISSN: | 15710653 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v50_n_p243_Bonomo |
Referencias:
- Bollobás, B., Thomason, A., Set colourings of graphs (1979) Discrete Mathematics, 25 (1), pp. 21-26
- Hahn, G., Hell, P., Poljak, S., On the ultimate independence ratio of a graph (1995) European Journal on Combinatorics, 16, pp. 253-261
- Larose, B., Laviolette, F., Tardif, C., On normal Cayley graphs and Hom-idempotent graphs (1998) European Journal of Combinatorics, 19, pp. 867-881
- Lovász, L., Kneser's conjecture, chromatic number and homotopy (1978) Journal of Combinatorial Theory, Series A, 25, pp. 319-324
- Sabidussi, G., Graphs with given group and given graph-theoretical properties (1957) Canadian Journal of Mathematics, 9, pp. 515-525
- Stahl, S., N-Tuple colorings and associated graphs (1976) Journal of Combinatorial Theory, Series B, 20, pp. 185-203
- Stahl, S., The multichromatic numbers of some Kneser graphs (1998) Discrete Mathematics, 185, pp. 287-291
Citas:
---------- APA ----------
Bonomo, F., Koch, I., Torres, P. & Valencia-Pabon, M. (2015) . k-tuple chromatic number of the cartesian product of graphs. Electronic Notes in Discrete Mathematics, 50, 243-248.http://dx.doi.org/10.1016/j.endm.2015.07.041
---------- CHICAGO ----------
Bonomo, F., Koch, I., Torres, P., Valencia-Pabon, M. "k-tuple chromatic number of the cartesian product of graphs" . Electronic Notes in Discrete Mathematics 50 (2015) : 243-248.http://dx.doi.org/10.1016/j.endm.2015.07.041
---------- MLA ----------
Bonomo, F., Koch, I., Torres, P., Valencia-Pabon, M. "k-tuple chromatic number of the cartesian product of graphs" . Electronic Notes in Discrete Mathematics, vol. 50, 2015, pp. 243-248.http://dx.doi.org/10.1016/j.endm.2015.07.041
---------- VANCOUVER ----------
Bonomo, F., Koch, I., Torres, P., Valencia-Pabon, M. k-tuple chromatic number of the cartesian product of graphs. Electron. Notes Discrete Math. 2015;50:243-248.http://dx.doi.org/10.1016/j.endm.2015.07.041
