Grafos Bipartidos Completos em ORTH[3, 3, t]
Resumo
Neste trabalho, nós investigamos sob quais condições um grafo Km,n pertence à classe ORTH[3, 3, t] introduzida por [Jamison and Mulder 2000]. Mostramos que K4,4 ∉ ORTH[3, 3, 4], corroborando uma conjectura de Jamison e Mulder em [Jamison and Mulder 2005]. O principal resultado deste trabalho é a prova da existência de um grafo G ⊆ Kn,n e G ∈ ORTH[3, 3, 2n - 3], se n é uma potência de 2 e n ≥ 4.
Referências
Bornstein, C. F., Coura Pinto, J. W., Rautenbach, D., and Szwarcfiter, J. L. (2017). Constant Threshold Intersection Graphs of Orthodox Paths in Trees. ArXiv e-prints.
Gavril, F. (1974). The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal of Combinatorial Theory, Series B, 16(1):47 – 56.
Golumbic, M. C. and Jamison, R. E. (1985a). Edge and vertex intersection of paths in a tree. Discrete Mathematics, 55(2):151 – 159.
Golumbic, M. C. and Jamison, R. E. (1985b). The edge intersection graphs of paths in a tree. Journal of Combinatorial Theory, Series B, 38(1):8 – 22.
Golumbic, M. C., Lipshteyn, M., and Stern, M. (2008). Equivalences and the complete hierarchy of intersection graphs of paths in a tree. Discrete Applied Mathematics, 156(17):3203 – 3215.
Jacobson, M., McMorris, F., and Mulder, H. (1991). An introduction to tolerance intersection graphs. Graph Theory, Combinatorics and Applications, 2:705–723.
Jamison, R. E. and Mulder, H. M. (2000). Tolerance intersection graphs on binary trees with constant tolerance 3. Discrete Mathematics, 215(1 - 3):115 – 131.
Jamison, R. E. and Mulder, H. M. (2005). Constant tolerance intersection graphs of subtrees of a tree. Discrete Mathematics, 290(1):27 – 46.
McMorris, F. R. and Scheinerman, E. R. (1991). Connectivity threshold for random chordal graphs. Graphs and Combinatorics, 7(2):177–181.
Gavril, F. (1974). The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal of Combinatorial Theory, Series B, 16(1):47 – 56.
Golumbic, M. C. and Jamison, R. E. (1985a). Edge and vertex intersection of paths in a tree. Discrete Mathematics, 55(2):151 – 159.
Golumbic, M. C. and Jamison, R. E. (1985b). The edge intersection graphs of paths in a tree. Journal of Combinatorial Theory, Series B, 38(1):8 – 22.
Golumbic, M. C., Lipshteyn, M., and Stern, M. (2008). Equivalences and the complete hierarchy of intersection graphs of paths in a tree. Discrete Applied Mathematics, 156(17):3203 – 3215.
Jacobson, M., McMorris, F., and Mulder, H. (1991). An introduction to tolerance intersection graphs. Graph Theory, Combinatorics and Applications, 2:705–723.
Jamison, R. E. and Mulder, H. M. (2000). Tolerance intersection graphs on binary trees with constant tolerance 3. Discrete Mathematics, 215(1 - 3):115 – 131.
Jamison, R. E. and Mulder, H. M. (2005). Constant tolerance intersection graphs of subtrees of a tree. Discrete Mathematics, 290(1):27 – 46.
McMorris, F. R. and Scheinerman, E. R. (1991). Connectivity threshold for random chordal graphs. Graphs and Combinatorics, 7(2):177–181.
Publicado
26/07/2018
Como Citar
BORNSTEIN, Claudson F.; PINTO, José Wilson C.; SZWARCFITER, Jayme L..
Grafos Bipartidos Completos em ORTH[3, 3, t]. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2018
.
p. 93-96.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2018.3167.
