Navegar

Colección

Datos Estadísticas

Artículo

Bonomo, F.; Koch, I.; Torres, P.; Valencia-Pabon, M. "k-tuple colorings of the Cartesian product of graphs" (2017) Discrete Applied Mathematics. 245:177-182
La versión final de este artículo es de uso interno. El editor solo permite incluir en el repositorio el artículo en su versión post-print. Por favor, si usted la posee enviela a
Consulte el artículo en la página del editor
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. © 2017 Elsevier B.V.

Registro:

Documento: Artículo
Título:k-tuple colorings 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 Industria, Universidad Nacional de General Sarmiento, Argentina
Universidad Nacional de Rosario and CONICET, Argentina
Université Paris-13, Sorbonne Paris Cité LIPN, CNRS UMR7030, Villetaneuse, France
Palabras clave:Cartesian product of graphs; Cayley graphs; Hom-idempotent graphs; k-tuple colorings; Kneser graphs; Color; Graphic methods; Set theory; Cartesian product of graphs; Cartesian Products; Cayley graphs; Chromatic number; Graph G; Idempotent; Kneser graph; Graph theory
Año:2017
Volumen:245
Página de inicio:177
Página de fin:182
DOI: http://dx.doi.org/10.1016/j.dam.2017.02.003
Título revista:Discrete Applied Mathematics
Título revista abreviado:Discrete Appl Math
ISSN:0166218X
CODEN:DAMAD
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v245_n_p177_Bonomo

Referencias:

  • Albertson, M.O., Collins, K.L., Homomorphisms of 3 -chromatic graphs (1985) Discrete Math., 54, pp. 127-132
  • Berge, C., Graphs and Hypergraphs (1976), North–Holland Amsterdam; Bollobás, B., Thomason, A., Set colourings of graphs (1979) Discrete Math., 25 (1), pp. 21-26
  • Erdős, P., Ko, C., Rado, R., Intersection theorems for systems of finite sets (1961) Quart. J. Math., 12, pp. 313-320
  • Hahn, G., Hell, P., Poljak, S., On the ultimate independence ratio of a graph (1995) European J. Combin., 16, pp. 253-261
  • Hilton, A.J.W., Milner, E.C., Some intersections theorems for systems of finite sets (1967) Quart. J. Math., 18, pp. 369-384
  • Larose, B., Laviolette, F., Tardif, C., On normal Cayley graphs and Hom-idempotent graphs (1998) European J. Combin., 19, pp. 867-881
  • Lovász, L., Kneser's conjecture, chromatic number and homotopy (1978) J. Combin. Theory Ser. A, 25, pp. 319-324
  • Sabidussi, G., Graphs with given group and given graph-theoretical properties (1957) Canad. J. Math., 9, pp. 515-525
  • Stahl, S., n-Tuple colorings and associated graphs (1976) J. Combin. Theory Ser. B, 20, pp. 185-203
  • Stahl, S., The multichromatic numbers of some Kneser graphs (1998) Discrete Math., 185, pp. 287-291
  • Vizing, V.G., Cartesian product of graphs (1963) Vych. Sys., 9, pp. 30-43. , (in Russian); In Computer Elements and Systems, 1–9:352–365, 1966 (English translation)

Citas:

---------- APA ----------
Bonomo, F., Koch, I., Torres, P. & Valencia-Pabon, M. (2017) . k-tuple colorings of the Cartesian product of graphs. Discrete Applied Mathematics, 245, 177-182.
http://dx.doi.org/10.1016/j.dam.2017.02.003
---------- CHICAGO ----------
Bonomo, F., Koch, I., Torres, P., Valencia-Pabon, M. "k-tuple colorings of the Cartesian product of graphs" . Discrete Applied Mathematics 245 (2017) : 177-182.
http://dx.doi.org/10.1016/j.dam.2017.02.003
---------- MLA ----------
Bonomo, F., Koch, I., Torres, P., Valencia-Pabon, M. "k-tuple colorings of the Cartesian product of graphs" . Discrete Applied Mathematics, vol. 245, 2017, pp. 177-182.
http://dx.doi.org/10.1016/j.dam.2017.02.003
---------- VANCOUVER ----------
Bonomo, F., Koch, I., Torres, P., Valencia-Pabon, M. k-tuple colorings of the Cartesian product of graphs. Discrete Appl Math. 2017;245:177-182.
http://dx.doi.org/10.1016/j.dam.2017.02.003