Show simple item record

Professor Guidedc.contributor.advisorStein, Maya
Authordc.contributor.authorRojas Anríquez, Alberto Benjamín 
Associate professordc.contributor.otherSoto San Martín, José
Associate professordc.contributor.otherMatamala Vásquez, Martín
Admission datedc.date.accessioned2019-04-11T21:26:45Z
Available datedc.date.available2019-04-11T21:26:45Z
Publication datedc.date.issued2019
Identifierdc.identifier.urihttp://repositorio.uchile.cl/handle/2250/168091
General notedc.descriptionTesis para optar al grado de Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadases_ES
General notedc.descriptionMemoria para optar al título de Ingeniero Civil Matemático
Abstractdc.description.abstractEl k-coloreo de vértices de un grafo es un ya conocido problema NP-completo, debido a esto, los esfuerzos se han concentrado en estudiar el problema restringido a ciertas clases de grafos, para intentar resolverlo en tiempo polinomial. Dentro de las clases de grafos más estudiada, están los grafos H-free, que son los grafos que no poseen un grafo isomorfo a H como subgrafo inducido. En el presente trabajo se investigó el problema de 3-coloreo en las clases de grafos (P_{2d+3},C_{≤ 2d-1})-free (donde C_{≤2d−1} = {C_{2k+1} ∣ k ∈ N y k ≤ d}), para d ≥ 3, obteniendo los siguientes resultados: Para el caso particular d = 3, se puede decidir si un grafo G de la clase ( P_9, C_5, C_3)-free posee un 3-coloreo (y encontrarlo si es que existe) en tiempo O(∣V (G)∣^4). Para todo d ≥ 3, se puede decidir si un grafo G de la clase (P_{2d+3},C_{≤ 2d-1}, C_8)-free posee un 3-coloreo (y encontrarlo si es que existe) en tiempo O(∣V (G)∣^4). Para todo d ≥ 3, se puede decidir si un grafo G de la clase ( P_{2d+3}, C_{≤2d−1})-free, que tiene un ciclo C de largo 2d + 3 como subgrafo inducido, posee un 3-coloreo (y encontrarlo si es que existe) en tiempo O(∣V (G)∣^4).es_ES
Patrocinadordc.description.sponsorshipCMM - Conicyt PIA AFB170001
Lenguagedc.language.isoeses_ES
Publisherdc.publisherUniversidad de Chilees_ES
Type of licensedc.rightsAttribution-NonCommercial-NoDerivs 3.0 Chile*
Link to Licensedc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/cl/*
Keywordsdc.subjectTeoría de grafoses_ES
Keywordsdc.subjectNúmeros Cromáticoses_ES
Keywordsdc.subjectH-freees_ES
Títulodc.title3-coloreo en grafos con caminos y ciclos prohibidoses_ES
Document typedc.typeTesises_ES
Catalogueruchile.catalogadorgmmes_ES
Departmentuchile.departamentoDepartamento de Ingeniería Matemáticaes_ES
Facultyuchile.facultadFacultad de Ciencias Físicas y Matemáticases_ES


Files in this item

Icon
Icon

This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivs 3.0 Chile
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 Chile