Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/331853
Type: TESE DIGITAL
Degree Level: Doutorado
Title: Partition problems in graphs and digraphs = Problemas de partição em grafos e digrafos
Title Alternative: Problemas de partição em grafos e digrafos
Author: Sambinelli, Maycon, 1988-
Advisor: Lee, Orlando, 1969-
Abstract: Resumo: Seja \(D\) um digrafo e \(k\) um inteiro positivo. Uma \emph{partição em caminhos} \(\mathcal{P}\) é uma coleção de caminhos tal que \(\{V(P) \: P \in \mathcal{P}\}\) é uma partição de \(V(D)\). A \emph{\(k\)-norma} de~\(\mathcal{P}\), denotada por \(|\mathcal{P}|_k\), é \(\sum_{P \in \mathcal{P}} \min\{|V(P)|, k\}\). Uma \emph{\(k\)-coloração parcial} \(\mathcal{C}\) de \(D\) é um empacotamento de \(V(D)\) tal que \(|\mathcal{C}| \leq k\) e todo \(C \in \mathcal{C}\) é um conjunto independente de~\(D\). Seja \(\pi_k(D) = \min \{|\mathcal{P}|_k \: \mathcal{P}\) é uma partição em caminhos de \(D\}\), \(V(\mathcal{C}) = \cup_{C \in \mathcal{C}} C\), e \(\alpha_k(D) =\) \( \max \{|V(\mathcal{C})|\) \( \: \mathcal{C}\) é uma \(k\)-coloração parcial de \(D\}\). Linial (1981) conjecturou que \(\pi_k(D) \leq \alpha_k(D)\) para todo digrafo \(D\). Verificamos essa conjectura para digrafos \emph{spine} e digrafos cujo grafo subjacente é série-paralelo. Uma \(k\)-coloração parcial \(\mathcal{C}\) é \emph{ortogonal} a uma partição em caminhos \(\mathcal{P}\) se todo caminho \(P \in \mathcal{P}\) intersecta \(\min \{|V(P)|, k\}\) conjuntos independentes em \(\mathcal{C}\). Berge (1982) conjecturou que se \(\mathcal{P}\) é uma partição em caminhos tal que \(|\mathcal{P}|_k = \pi_k(D)\), então existe uma \(k\)-coloração parcial de \(D\) ortogonal à \(\mathcal{P}\). Verificamos essa conjectura para digrafos \emph{locally in-semicomplete} e para partições em caminhos contendo apenas dois caminhos. Uma \emph{coloração} \(\mathcal{C}\) é uma partição de \(V(D)\) onde cada \(C \in \mathcal{C}\) é um conjunto independente. A \emph{\(k\)-norma} de \(\mathcal{C}\), denotada por \(|\mathcal{C}|_k\), é \(\sum_{C \in \mathcal{C}} \min\{|C|, k\}\). Um \emph{\(k\)-empacotamento de caminhos} \(\mathcal{P}\) é uma coleção de caminhos tal que \(\{V(P) \: P \in \mathcal{P}\}\) é um empacotamento de \(V(D)\) e \(|\mathcal{P}| \leq k\). Seja \(V(\mathcal{P}) = \cup_{P \in \mathcal{P}} V(P)\). Dizemos que \(\mathcal{P}\) é \emph{máximo} se \(|V(\mathcal{P})| \geq |V(\mathcal{P}')|\) para todo $k$-empacotamento de caminhos \(\mathcal{P}'\) de \(D\). Uma coloração \(\mathcal{C}\) de \(D\) é \emph{ortogonal} a um \(k\)-empacotamento de caminhos se toda cor \(C \in \mathcal{C}\) intersecta \(\min \{|C|, k\}\) caminhos em \(\mathcal{P}\). Aharoni, Hartman, e Hoffman (1985) conjecturaram que se \(\mathcal{P}\) é um \(k\)-empacotamento de caminhos máximo, então existe uma coloração de $D$ ortogonal à \(\mathcal{P}\). Verificamos essa conjectura para digrafos \emph{locally in-semicomplete}. Dado um \(S \subseteq V(D)\), uma partição em caminhos \(\mathcal{P}\) de \(D\) é uma \emph{\(S\)-partição em caminhos} se \(|V(P) \cap S| = 1\) para todo \(P \in \mathcal{P}\). Dizemos que \(D\) satisfaz a \emph{propriedade \(\alpha\)} se existe uma \(S\)-partição em caminhos para todo conjunto independente máximo \(S\) de \(D\), e que \(D\) é \emph{\(\alpha\)-diperfeito} se todo subdigrafo induzido de \(D\) satisfaz a propriedade \(\alpha\). Um digrafo \(C\) é um \emph{ciclo ímpar anti-orientado} se (i) o grafo subjacente de \(C\) é um ciclo \(x_1x_2 \cdots x_{2k + 1}x_1\), onde \(k \in \mathbb{Z}\) e \(k \geq 2\), e (ii) cada um dos vértices \(x_1, x_2, x_3, x_4, x_6,\) \(x_8, \ldots, x_{2k}\) é ou uma fonte ou um sorvedouro. Berge~(1982) conjecturou que um digrafo é \(\alpha\)-diperfeito se, e somente se, ele não contém um ciclo ímpar anti-orientado como subdigrafo induzido. Verificamos essa conjectura para digrafos \emph{locally in-semicomplete} e para digrafos cujo grafo subjacente é série-paralelo. Além disso, propomos uma variação desta conjectura e a verificamos para digrafos cujo grafo subjacente é perfeito ou série-paralelo, para digrafos \emph{locally in-semicomplete}, e para digrafos $2$-semi-simétricos. Seja \(G\) um grafo. Uma coleção de caminhos \(\mathcal{P} = \{P_i\}_{i = 1}^\ell\) é uma \emph{decomposição em caminhos} de \(G\) se \(\{E(P_i)\}_{i = 1}^\ell\) é uma partição de \(E(G)\). Seja \({\rm pn}(G) = \min \{|\mathcal{P}| \: \mathcal{P}\) é uma decomposição em caminhos de \(G\}\). Gallai~(1968) conjecturou que, para todo grafo conexo \(G\), \({\rm pn}(G) \leq \lceil |V(G)| /2\rceil\). Verificamos esta conjectura para grafos planares com cintura pelo menos \(6\), grafos com largura arbórea no máximo \(3\), e grafos com grau máximo no máximo~\(4\)

Abstract: Let \(D\) be a digraph and \(k\) be a positive integer. A \emph{path partition} \(\mathcal{P}\) is a collection of paths in \(D\) such that \(\{V(P) \: P \in \mathcal{P}\}\) is a partition of \(V(D)\). The \emph{\(k\)-norm} of \(\mathcal{P}\), denoted by~\(|\mathcal{P}|_k\), is \(\sum_{P \in \mathcal{P}} \min\{|V(P)|, k\}\). A \emph{partial \(k\)-coloring} \(\mathcal{C}\) of \(D\) is a packing of \(V(D)\) such that \(|\mathcal{C}| \leq k\) and each \(C \in \mathcal{C}\) is a stable set. Let \(\pi_k(D) = \min \{|\mathcal{P}|_k \: \mathcal{P}\) is a path partition of \(D\}\), \(V(\mathcal{C}) = \cup_{C \in \mathcal{C}} C\), and \(\alpha_k(D) = \max \{|V(\mathcal{C})| \: \mathcal{C}\) is a partial \(k\)-coloring of \(D\}\). Linial (1981) conjectured that \(\pi_k(D) \leq \alpha_k(D)\) for every digraph \(D\). We verify this conjecture for spine digraphs and digraphs whose underlying graph is series-parallel. A partial \(k\)-coloring~\(\mathcal{C}\) is \emph{orthogonal} to a path partition \(\mathcal{P}\) if every path \(P \in \mathcal{P}\) meets \(\min \{|V(P)|, k\}\) stable sets in \(\mathcal{C}\). Berge (1982) conjectured that if \(\mathcal{P}\) is a path partition such that \(|\mathcal{P}|_k = \pi_k(D)\), then there exists a partial \(k\)-coloring orthogonal to \(\mathcal{P}\). We verify Berge's conjecture for locally in-semicomplete digraphs and for path partitions containing only two paths. A coloring \(\mathcal{C}\) is a partition of \(V(D)\) where each \(C \in \mathcal{C}\) is a stable set of \(D\). The \emph{\(k\)-norm} of~\(\mathcal{C}\), denoted by \(|\mathcal{C}|_k\), is \(\sum_{C \in \mathcal{C}} \min\{|C|, k\}\). A \emph{path \(k\)-pack} \(\mathcal{P}\) is a collection of paths such that \(\{V(P) \: P \in \mathcal{P}\}\) is a packing of \(V(D)\) and \(|\mathcal{P}| \leq k\). Let \(V(\mathcal{P}) = \cup_{P \in \mathcal{P}} V(P)\). We say that \(\mathcal{P}\) is \emph{maximum} if \(|V(\mathcal{P})| \geq |V(\mathcal{P}')|\) for every path \(k\)-pack \(\mathcal{P}'\) of \(D\). A coloring~\(\mathcal{C}\) is \emph{orthogonal} to a path \(k\)-pack \(\mathcal{P}\) if every color class \(C \in \mathcal{C}\) meets \(\min \{|C|, k\}\) paths in~\(\mathcal{P}\). Aharoni, Hartman, and Hoffman (1985) conjectured that if~\(\mathcal{P}\) is a maximum path \(k\)-pack, then there exists a coloring orthogonal to \(\mathcal{P}\). We verify this conjecture for locally in-semicomplete digraphs. Given a set of vertices \(S \subseteq V(D)\), we say that \(\mathcal{P}\) is an \emph{\(S\)-path partition} of \(D\) if \(\mathcal{P}\) is a path partition of \(D\) such that \(|V(P) \cap S| = 1\) for every \(P \in \mathcal{P}\). We say that \(D\) satisfies the \emph{\(\alpha\)-property} if there exists an \(S\)-path partition for every maximum stable set \(S\) of \(D\), and we say that \(D\) is \emph{\(\alpha\)-diperfect} if every induced subdigraph of \(D\) satisfies the \(\alpha\)-property. A digraph \(C\) is an \emph{anti-directed odd cycle} if (i) the underlying graph of \(C\) is a cycle \(x_1x_2 \cdots x_{2k + 1}x_1\), where \(k \in \mathbb{Z}\) and \(k \geq 2\), and (ii) each of the vertices \(x_1, x_2, x_3, x_4, x_6,\) \(x_8, \ldots, x_{2k}\) is either a source or a sink. Berge (1982) conjectured that a digraph is \(\alpha\)-diperfect if, and only if, it contains no induced anti-directed odd cycle. We verify this conjecture for locally in-semicomplete digraphs and digraphs whose underlying graph is series-parallel. In addition, we propose a conjecture similar to this one and verify it for digraphs whose underlying graph is perfect or series-parallel, locally in-semicomplete digraphs, and for \(2\)-semi-symmetric digraphs. Let \(G\) be a graph. A collection of paths \(\mathcal{P} = \{P_i\}_{i = 1}^\ell\) is a \emph{path decomposition} of \(G\) if \(\{E(P_i)\}_{i = 1}^\ell\) is a partition of \(E(G)\). Let \({\rm pn}(G) = \min \{|\mathcal{P}| \: \mathcal{P}\) is a path decomposition of \(G\}\). Gallai~(1968) conjectured that, for every connected graph \(G\), \({\rm pn}(G) \leq \lceil |V(G)| /2 \rceil\). We verify this conjecture for planar graphs with girth at least \(6\), graphs with treewidth at most \(3\), and graphs with maximum degree at most \(4\)
Subject: Análise combinatória
Teoria dos grafos
Grafos orientados
Language: Inglês
Editor: [s.n.]
Date Issue: 2018
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Sambinelli_Maycon_D.pdf1.17 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.