k-tuple colorings of the Cartesian product of graphs | ||
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación | |
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación | |
| dc.conicet.organizacion | Universidad Nacional de General Sarmiento. Instituto de Industria | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario | |
| dc.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura | |
| dc.conicet.organizacion | Centre National de la Recherche Scientifique | |
| dc.conicet.organizacion | Universite de Paris 13-Nord | |
| dc.contributor.author | Bonomo, Flavia | |
| dc.contributor.author | Koch, Ivo Valerio | |
| dc.contributor.author | Torres, Pablo | |
| dc.contributor.author | Valencia Pabon, Mario | |
| dc.date.issued | 2017-01 | |
| dc.description.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. | es |
| dc.description.fil | Fil: Bonomo, Flavia. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina | |
| dc.description.fil | Fil: Koch, Ivo Valerio. Universidad Nacional de General Sarmiento. Instituto de Industria; Argentina | |
| dc.description.fil | Fil: Torres, Pablo. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina | |
| dc.description.fil | Fil: Valencia Pabon, Mario. Universite de Paris 13-Nord; Francia. Centre National de la Recherche Scientifique; Francia | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Bonomo, Flavia; Koch, Ivo Valerio; Torres, Pablo; Valencia Pabon, Mario; k-tuple colorings of the Cartesian product of graphs; Elsevier Science; Discrete Applied Mathematics; 245; 1-2017; 177-182 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0166-218X | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/97048 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.pagination | 177-182 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Discrete Applied Mathematics | es |
| dc.journal.volume | 245 | es |
| dc.language.iso | eng | es |
| dc.publisher | Elsevier Science | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.dam.2017.02.003 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0166218X17300872 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/2.5/ar/ | * |
| dc.subject | CARTESIAN PRODUCT OF GRAPHS | es |
| dc.subject | CAYLEY GRAPHS | es |
| dc.subject | HOM-IDEMPOTENT GRAPHS | es |
| dc.subject | K-TUPLE COLORINGS | es |
| dc.subject | KNESER GRAPHS | es |
| dc.subject.classification | Ciencias de la Computación | es |
| dc.subject.classification | Ciencias de la Computación e Información | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.subject.classification | Matemática Aplicada | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | k-tuple colorings of the Cartesian product of graphs | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.be221c24-4bb3-4458-b1ff-2a6268333706_X.pdf
- Tamaño:
- 290.47 KB
- Formato:
- Adobe Portable Document Format
- Descripción: