On Tuza's conjecture in even co-chain graphs
Resumo
In 1981, Tuza conjectured that the cardinality of a minimum set of edges that intersects every triangle of a graph is at most twice the cardinality of a maximum set of edge-disjoint triangles. This conjecture has been proved for several important graph classes, as planar graphs, tripartite graphs, among others. However, it remains open on other important classes of graphs, as chordal graphs. Furthermore, it remains open for main subclasses of chordal graphs, as split graphs and interval graphs. In this paper, we show that Tuza’s conjecture is valid for even co-chain graphs, a known subclass of interval graphs.
Palavras-chave:
co-chain graph, triangle packing set, triangle hitting set, clique, independent set
Referências
Bonamy, M., Bozyk, ., Grzesik, A., Hatzel, M., Masarík, T., Novotná, J., and Okrasa, K. (2021). Tuza’s conjecture for threshold graphs. In Extended Abstracts EuroComb 2021, pages 765–771. Springer.
Botler, F., Fernandes, C. G., and Gutiérrez, J. (2021). On tuza’s conjecture for triangulations and graphs with small treewidth. Discrete Mathematics, 344(4):112281.
Boyac, A., Ekim, T., and Shalom, M. (2018). The maximum cardinality cut problem in co-bipartite chain graphs. J. Comb. Optim., 35(1):250–265.
Brandstädt, A., Le, V. B., and Spinrad, J. P. (1999). Graph classes: a survey. SIAM.
Cui, Q. and Wang, J. (2009). Maximum bipartite subgraphs of cubic triangle-free planar graphs. Discrete Mathematics, 309(5):1091–1111.
Feder, T. and Subi, C. S. (2012). Packing edge-disjoint triangles in given graphs. In Electron. Colloquium Comput. Complex., volume 19, page 13.
Haxell, P. E. (1999). Packing and covering triangles in graphs. Discrete Mathematics, 195(1):251–254.
Haxell, P. E., Kostochka, A., and Thomassé, S. (2012). Packing and covering triangles in K4-free planar graphs. Graphs and Combinatorics, 28(5):653–662.
Kijima, S., Otachi, Y., Saitoh, T., and Uno, T. (2012). Subgraph isomorphism in graph classes. Discrete Mathematics, 312(21):3164–3173.
Tuza, Z. (1981). Conjecture in: finite and infinite sets. In Proc. Colloq. Math. Soc. J. Bolyai (Eger, Hungary, 1981), volume 37, page 888.
Tuza, Z. (1990). A conjecture on triangles of graphs. Graphs and Combinatorics, 6(4):373–380.
Botler, F., Fernandes, C. G., and Gutiérrez, J. (2021). On tuza’s conjecture for triangulations and graphs with small treewidth. Discrete Mathematics, 344(4):112281.
Boyac, A., Ekim, T., and Shalom, M. (2018). The maximum cardinality cut problem in co-bipartite chain graphs. J. Comb. Optim., 35(1):250–265.
Brandstädt, A., Le, V. B., and Spinrad, J. P. (1999). Graph classes: a survey. SIAM.
Cui, Q. and Wang, J. (2009). Maximum bipartite subgraphs of cubic triangle-free planar graphs. Discrete Mathematics, 309(5):1091–1111.
Feder, T. and Subi, C. S. (2012). Packing edge-disjoint triangles in given graphs. In Electron. Colloquium Comput. Complex., volume 19, page 13.
Haxell, P. E. (1999). Packing and covering triangles in graphs. Discrete Mathematics, 195(1):251–254.
Haxell, P. E., Kostochka, A., and Thomassé, S. (2012). Packing and covering triangles in K4-free planar graphs. Graphs and Combinatorics, 28(5):653–662.
Kijima, S., Otachi, Y., Saitoh, T., and Uno, T. (2012). Subgraph isomorphism in graph classes. Discrete Mathematics, 312(21):3164–3173.
Tuza, Z. (1981). Conjecture in: finite and infinite sets. In Proc. Colloq. Math. Soc. J. Bolyai (Eger, Hungary, 1981), volume 37, page 888.
Tuza, Z. (1990). A conjecture on triangles of graphs. Graphs and Combinatorics, 6(4):373–380.
Publicado
31/07/2022
Como Citar
CHAHUA, Luis; GUTIÉRREZ, Juan.
On Tuza's conjecture in even co-chain graphs. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 7. , 2022, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 109-112.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2022.223185.
