skip to main content
Idioma:
Primo Advanced Search
Primo Advanced Search Query Term
Primo Advanced Search Query Term
Primo Advanced Search Query Term
Primo Advanced Search prefilters
Busca Simples

Graph colorings and digraph subdivisions

Moura, Phablo Fernando Soares

Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Matemática e Estatística 2017-03-30

Acesso online. A biblioteca também possui exemplares impressos.

  • Título:
    Graph colorings and digraph subdivisions
  • Autor: Moura, Phablo Fernando Soares
  • Orientador: Wakabayashi, Yoshiko
  • Assuntos: Coloração De Grafos; Recoloração Convexa; Poliedro; Orientação De Grafos; Inaproximabilidade; Subdivisão De Digrafos; Geração De Colunas; Complexidade Computacional; Graph Coloring; Digraph Subdivision; Inapproximability; Convex Recoloring; Computational Complexity; Polyhedral Study; Column Generation; Graph Orientation
  • Notas: Tese (Doutorado)
  • Descrição: The vertex coloring problem is a classic problem in graph theory that asks for a partition of the vertex set into a minimum number of stable sets. This thesis presents our studies on three vertex (re)coloring problems on graphs and on a problem related to a long-standing conjecture on subdivision of digraphs. Firstly, we address the convex recoloring problem in which an arbitrarily colored graph G is given and one wishes to find a minimum weight recoloring such that each color class induces a connected subgraph of G. We show inapproximability results, introduce an integer linear programming (ILP) formulation that models the problem and present some computational experiments using a column generation approach. The k-fold coloring problem is a generalization of the classic vertex coloring problem and consists in covering the vertex set of a graph by a minimum number of stable sets in such a way that every vertex is covered by at least k (possibly identical) stable sets. We present an ILP formulation for this problem and show a detailed polyhedral study of the polytope associated with this formulation. The last coloring problem studied in this thesis is the proper orientation problem. It consists in orienting the edge set of a given graph so that adjacent vertices have different in-degrees and the maximum in-degree is minimized. Clearly, the in-degrees induce a partition of the vertex set into stable sets, that is, a coloring (in the conventional sense) of the vertices. Our contributions in this problem are on hardness and upper bounds for bipartite graphs. Finally, we study a problem related to a conjecture of Mader from the eighties on subdivision of digraphs. This conjecture states that, for every acyclic digraph H, there exists an integer f(H) such that every digraph with minimum out-degree at least f(H) contains a subdivision of H as a subdigraph. We show evidences for this conjecture by proving that it holds for some particular classes of acyclic digraphs.
  • DOI: 10.11606/T.45.2017.tde-23052017-100619
  • Editor: Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Matemática e Estatística
  • Data de criação/publicação: 2017-03-30
  • Formato: Adobe PDF
  • Idioma: Inglês
Links
Voltar para lista de resultados
Ir para página anteriorAnterior Resultado  4 AvançarIr para próxima página

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.