Browsing by Author "Stein, Maya"

Now showing items 1-9 of 9

    • The approximate loebl-komlos-sos conjecture and embedding trees in sparse graphs 
      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 ...
    • b-Coloring is NP-hard on Co-bipartite Graphs and Polytime Solvable on Tree-Cographs 
      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 ...
    • Complexity of splits reconstruction for low-degree trees 
      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 ...
    • Convex p-partitions of bipartite graphs 
      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 ...
    • FORCING LARGE COMPLETE (TOPOLOGICAL) MINORS IN INFINITE GRAPHS∗ 
      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 ...
    • Geodesic stability for memoryless binary long-lived consensus 
      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 ...
    • Linear and projective boundaries in HNN-extensions and distortion phenomena 
      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 ...
    • List Edge-Coloring and Total Coloring in Graphs of Low Treewidth 
      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. ...
    • t-perfection is always strong for claw-free graphs 
      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. ...