Browsing by Author "Stein, Maya"
Now showing items 1-20 of 26
-
(Universidad de Chile, 2019)El 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 ...
-
(Amer Inst Mathematical Sciences, 2015)Loebl, Komlos and Sos conjectured that every n-vertex graph G with at least n/2 vertices of degree at least k contains each tree T of order k + 1 as a subgraph. We give a sketch of a proof of the approximate version of ...
-
(Universidad de Chile, 2022)El presente trabajo define un modelo de subgrafos aleatorios de torneos $T_{p}$ y desarrolla técnicas que combinan ideas de grafos aleatorios, de torneos y de teoría extremal para encontrar ciertas familias de subestructuras ...
-
(Springer, 2015)A b-coloring of a graph is a proper coloring such that every color class contains a vertex that is adjacent to all other color classes. The b-chromatic number of a graph , denoted by , is the maximum number such that admits ...
-
(Universidad de Chile, 2020)En este trabajo se estudian problemas de coloración en grafos pigmentados. Un grafo pigmentado es una tupla $(G,c)$ con $G$ un grafo y $c:E(G)\to \NN$ una asignación de pigmentos en las aristas. El primer capítulo se centra ...
-
(Elsevier, 2015)Given a vertex-weighted tree T , the split of an edge e in T is the minimum over the weights of the two trees obtained by removing e from T , where the weight of a tree is the sum of weights of its vertices. Given a set ...
-
(Elsevier, 2016)A set of vertices X of a graph G is convex if no shortest path between two vertices in X contains a vertex outside X. We prove that for fixed p >= 1, all partitions of the vertex set of a bipartite graph into p convex sets ...
-
(Universidad de Chile, 2014)La presente memoria tiene como objetivo un estudio general sobre componentes monocromáticas en multicoloreos de aristas de grafos completos, o dicho de otro modo, un coloreo de aristas de multigrafos completos. En particular, ...
-
(Universidad de Chile, 2022)La pregunta que dio inicio a esta tesis fue decidir si semigrado mínimo mayor a $\frac k2$ en un grafo orientado garantiza tener como subgrafo a cualquier camino orientado de $k$ aristas. Este enunciado correspondería a ...
-
(Universidad de Chile, 2014)Se estudia la estructura de grafos completos de tamaño apropiado, con una coloreación de sus aristas en dos colores, de manera tal que no presentan como subgrafos monocromáticos a ciertos tipos de grafos específicos. En ...
-
(Society for Industrial and Applied Mathematics, 2013)It is well known that in finite graphs, large complete minors/topological minors can be forced by assuming a large average degree. Our aim is to extend this fact to infinite graphs. For this, we generalize the notion of ...
-
(Universidad de Chile, 2013)Dos grafos son gemelos si son mutuamente subgrafos entre sí. En grafos finitos la única forma de que dos grafos sean mutuamente subgrafos entre sí es que sean isomorfos. Sin embargo, en grafos infinitos existen grafos que ...
-
(Elsevier, 2015)The determination of the (in-)stability of the long-lived consensus problem is a fundamental open problem in distributed systems. We concentrate on the memoryless binary case with geodesic paths. For this case, we offer a ...
-
(Universidad de Chile, 2018)The main focus of this thesis is the study of monochromatic cycle partitions in uniform hypergraphs. The first part deals with Berge-cycles. Extending a result of Rado to hypergraphs, we prove that for all $r,k \in \N$ ...
-
(De Gruyter, 2015)Linear and projective boundaries of Cayley graphs were introduced in [6] as quasi-isometry invariant boundaries of finitely generated groups. They consist of forward orbits g1 D ¹gi W i 2 Nº, or orbits g 1 D ¹gi W i 2 ...
-
(Wiley & Sons, 2016)We prove that the list chromatic index of a graph of maximum degree Delta and treewidth <= root 2 Delta -3 is Delta; and that the total chromatic number of a graph of maximum degree and treewidth <= Delta/3+1 is Delta+1. ...
-
(Universidad de Chile, 2023)Si coloreamos con $r$ colores las aristas de un grafo con grado mínimo $n/2 + 1200r\log(n)$ es posible construir una partición del conjunto de vértices, compuesta únicamente ciclos monocromáticos, de tamaño $O(r^2)$. Este ...
-
(Universidad de Chile, 2017)The first part of this thesis concerns monochromatic cycle partitions. We make the following three contributions. Our first result is that for any colouring of the edges of the complete bipartite graph $K_{n,n}$ with 3 ...
-
(Universidad de Chile, 2020)En 1991 Erdos, Gyárfás y Pyber conjeturaron que para todo r-coloreo de un grafo completo Kn este puede ser particionado en a lo más r - 1 árboles monocromáticos. Paralelamente Gyárfás y Lehel conjeturaron un resultado ...
-
(Universidad de Chile, 2017)Un coloreo de aristas de un grafo se llama γ-promedio si es que el número promedio de colores incidentes a cada vértice es a lo más γ. Dados n, m enteros positivos y γ un real positivo, el número de Turán promedio coloreado ...
