k-tuple colorings of the Cartesian product of graphs
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 t...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , , |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
Elsevier B.V.
2017
|
| Materias: | |
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 05196caa a22007577a 4500 | ||
|---|---|---|---|
| 001 | PAPER-13070 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518204319.0 | ||
| 008 | 190410s2017 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-85014588554 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 030 | |a DAMAD | ||
| 100 | 1 | |a Bonomo, F. | |
| 245 | 1 | 0 | |a k-tuple colorings of the Cartesian product of graphs |
| 260 | |b Elsevier B.V. |c 2017 | ||
| 270 | 1 | 0 | |m Torres, P.; Universidad Nacional de Rosario and CONICETArgentina; email: ptorres@fceia.unr.edu.ar |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Albertson, M.O., Collins, K.L., Homomorphisms of 3 -chromatic graphs (1985) Discrete Math., 54, pp. 127-132 | ||
| 504 | |a 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 | ||
| 504 | |a Erdős, P., Ko, C., Rado, R., Intersection theorems for systems of finite sets (1961) Quart. J. Math., 12, pp. 313-320 | ||
| 504 | |a Hahn, G., Hell, P., Poljak, S., On the ultimate independence ratio of a graph (1995) European J. Combin., 16, pp. 253-261 | ||
| 504 | |a Hilton, A.J.W., Milner, E.C., Some intersections theorems for systems of finite sets (1967) Quart. J. Math., 18, pp. 369-384 | ||
| 504 | |a Larose, B., Laviolette, F., Tardif, C., On normal Cayley graphs and Hom-idempotent graphs (1998) European J. Combin., 19, pp. 867-881 | ||
| 504 | |a Lovász, L., Kneser's conjecture, chromatic number and homotopy (1978) J. Combin. Theory Ser. A, 25, pp. 319-324 | ||
| 504 | |a Sabidussi, G., Graphs with given group and given graph-theoretical properties (1957) Canad. J. Math., 9, pp. 515-525 | ||
| 504 | |a Stahl, S., n-Tuple colorings and associated graphs (1976) J. Combin. Theory Ser. B, 20, pp. 185-203 | ||
| 504 | |a Stahl, S., The multichromatic numbers of some Kneser graphs (1998) Discrete Math., 185, pp. 287-291 | ||
| 504 | |a 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) | ||
| 520 | 3 | |a 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. |l eng | |
| 536 | |a Detalles de la financiación: JCJC CombPhysMat2Tens | ||
| 536 | |a Detalles de la financiación: PICT 2012-1324 | ||
| 536 | |a Detalles de la financiación: Secretaría de Ciencia y Técnica, Universidad de Buenos Aires, 20020130100808BA | ||
| 536 | |a Detalles de la financiación: PIP 112-201201-00450CO | ||
| 536 | |a Detalles de la financiación: Partially supported by MathAmSud Project 13MATH-07 (Argentina?Brazil?Chile?France), UBACyT grant 20020130100808BA, CONICET PIP 112-201201-00450CO, ANPCyT PICT 2012-1324 (Argentina), and by the French ANR JCJC CombPhysMat2Tens grant. | ||
| 593 | |a CONICET and DC, FCEN, Universidad de Buenos Aires, Argentina | ||
| 593 | |a Instituto de Industria, Universidad Nacional de General Sarmiento, Argentina | ||
| 593 | |a Universidad Nacional de Rosario and CONICET, Argentina | ||
| 593 | |a Université Paris-13, Sorbonne Paris Cité LIPN, CNRS UMR7030, Villetaneuse, France | ||
| 690 | 1 | 0 | |a CARTESIAN PRODUCT OF GRAPHS |
| 690 | 1 | 0 | |a CAYLEY GRAPHS |
| 690 | 1 | 0 | |a HOM-IDEMPOTENT GRAPHS |
| 690 | 1 | 0 | |a K-TUPLE COLORINGS |
| 690 | 1 | 0 | |a KNESER GRAPHS |
| 690 | 1 | 0 | |a GRAPHIC METHODS |
| 690 | 1 | 0 | |a SET THEORY |
| 690 | 1 | 0 | |a CARTESIAN PRODUCT OF GRAPHS |
| 690 | 1 | 0 | |a CARTESIAN PRODUCTS |
| 690 | 1 | 0 | |a CAYLEY GRAPHS |
| 690 | 1 | 0 | |a CHROMATIC NUMBER |
| 690 | 1 | 0 | |a GRAPH G |
| 690 | 1 | 0 | |a IDEMPOTENT |
| 690 | 1 | 0 | |a KNESER GRAPH |
| 690 | 1 | 0 | |a GRAPH THEORY |
| 650 | 1 | 7 | |2 spines |a COLOR |
| 700 | 1 | |a Koch, I. | |
| 700 | 1 | |a Torres, P. | |
| 700 | 1 | |a Valencia-Pabon, M. | |
| 773 | 0 | |d Elsevier B.V., 2017 |g v. 245 |h pp. 177-182 |p Discrete Appl Math |x 0166218X |w (AR-BaUEN)CENRE-310 |t Discrete Applied Mathematics | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-85014588554&doi=10.1016%2fj.dam.2017.02.003&partnerID=40&md5=20f6329240cec33bc8a67f40ed24e3f3 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1016/j.dam.2017.02.003 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_0166218X_v245_n_p177_Bonomo |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v245_n_p177_Bonomo |y Registro en la Biblioteca Digital |
| 961 | |a paper_0166218X_v245_n_p177_Bonomo |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 963 | |a VARI | ||
| 999 | |c 74023 | ||