Defesa de Doutorado de Maycon Sambinelli

Título do Trabalho
Partition problems in graphs and digraphs
Candidato(a)
Maycon Sambinelli
Nível
Doutorado
Data
Add to Calender 2018-04-24 00:00:00 2018-04-24 00:00:00 Defesa de Doutorado de Maycon Sambinelli Partition problems in graphs and digraphs Sala 85 IC 2 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
10:30
Local
Sala 85 IC 2
Orientador(a)
Orlando Lee
Banca Examinadora

Condição

Titulares  (Professores Doutores)

Unidade/Instituição

Orientador/Presidente

Orlando Lee

IC/UNICAMP

Membro

Daniel Morgato Martin

CMCC/UFABC

Membro

Guilherme Oliveira Mota

CMCC/UFABC

Membro

Simone Dantas de Souza

IM/UFF

Membro

João Meidanis

IC/UNICAMP

 

Condição

Suplentes (Professores Doutores)

Unidade/Instituição

Suplente

Phablo Fernando Soares Moura

IC/UNICAMP

Suplente

Ricardo Dahab

IC/UNICAMP

Suplente

José Coelho de Pina

IME/USP

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) \colon 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}\) é 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 \colon \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})|\) \( \colon \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 é serie-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) \colon 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 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\), (ii) \(k \geq 2\), (iii) o caminho mais longo em \(C\) tem comprimento \(2\), e (iv) 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 é serie-paralelo. Além disso, propomos uma conjectura similar a esta e a verificamos para digrafos cujo grafo subjacente é perfeito ou serie-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 \(pn(G) = \min \{|\mathcal{P}| \colon \mathcal{P}\) é uma decomposição em caminhos de \(G\}\). Gallai~(1968) conjecturou que, para todo grafo conexo \(G\), \(pn(G) \leq \lceil |V(G)| /2 \rceil\). Verificamos esta conjectura para grafos planares com cintura ao menos \(6\), grafos com largura arbórea no máximo \(3\), e grafos com grau máximo no máximo \(4\).