Now showing items 1-20 of 22

    • Rojas Anríquez, Alberto Benjamín (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 ...
    • Hladký, Jan; Piguet, Diana; Simonovits, Miklós; Stein, Maya; Szemerédi, Endre (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 ...
    • Bonomo, Flavia; Schaudt, Oliver; Stein, Maya; Valencia Pabón, Mario (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 ...
    • Maldonado Henríquez, Julio Cristopher (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 ...
    • Gaspers, Serge; Liedloff, Mathieu; Stein, Maya; Suchane, Karol (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 ...
    • Grippo, Luciano N.; Matamala Vásquez, Martín; Safe, Martín D.; Stein, Maya (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 ...
    • Bustamante Franco, Sebastián Felipe (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, ...
    • Sanhueza Matamala, Nicolás Ignacio (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 ...
    • Stein, Maya; Zamora, José (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 ...
    • Araneda Galarce, Sergio Andrés (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 ...
    • Fernandes, Cristina G.; Stein, Maya (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 ...
    • Bustamante Franco, Sebastián Felipe (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$ ...
    • Krön, Bernhard; Lehnert, Jörg; Stein, Maya (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 ...
    • Bruhn, Henning; Lang, Richard; Stein, Maya (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. ...
    • Lang, Richard Johannes (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 ...
    • Fernández Morales, Camila Javiera (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 ...
    • Piga Díaz, Simón Cristóbal (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 ...
    • Contreras Salinas, Felipe Guillermo (Universidad de Chile, 2016)
      Un conjunto de vértices de un grafo se dice convexo si contiene a los vértices de todos los caminos mínimos entre sus vértices. El problema de determinar si un grafo tiene una partición en p conjuntos convexos es NP-completo, ...
    • Bruhn, Henning; Stein, Maya (SIAM PUBLICATIONS, 2010)
      A connected graph G is called t-perfect if its stable set polytope is determined by the non-negativity, edge and odd-cycle inequalities. More- over, G is called strongly t-perfect if this system is totally dual inte- gral. ...
    • Flores Dubó, Freddy Ignacio (Universidad de Chile, 2021)
      Una doble estrella $S(n,m)$ es el grafo obtenido a partir de una estrella con $n$ hojas y otra estrella con $m$ hojas al unir sus centros con una arista. Sea $R(S(n,m))$ el número de Ramsey, definido como el mínimo $N$ tal ...