Perfect forests in graphs and their extensions

Autor: Gutin, Gregory, Yeo, Anders

Publikováno v: Gutin, G & Yeo, A 2021, Perfect Forests in Graphs and Their Extensions . in F Bonchi & S J Puglisi (eds), 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021 ., 54, Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 202, 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, Tallinn, Estonia, 23/08/2021 . https://doi.org/10.4230/LIPIcs.MFCS.2021.54

Let G be a graph on n vertices. For i ∈ {0,1} and a connected graph G, a spanning forest F of G is called an i-perfect forest if every tree in F is an induced subgraph of G and exactly i vertices of F have even degree (including zero). An i-perfect

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5e7db594be3d309301291a8983036891
https://doi.org/10.1002/jgt.22841

The Number of Edges in Maximal 2-planar Graphs

Autor: Hoffmann, Michael, M. Reddy, Meghana

Publikováno v: 39th International Symposium on Computational Geometry

A graph is 2-planar if it has local crossing number two, that is, it can be drawn in the plane such that every edge has at most two crossings. A graph is maximal 2-planar if no edge can be added such that the resulting graph remains 2-planar. A 2-pla

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2fc2f2c9840264a9432551615b283b17

On the geometric thickness of 2-degenerate graphs

Autor: Jain, Rahul, Ricci, Marco, Rollin, Jonathan, Schulz, André

A graph is 2-degenerate if every subgraph contains a vertex of degree at most 2. We show that every 2-degenerate graph can be drawn with straight lines such that the drawing decomposes into 4 plane forests. Therefore, the geometric arboricity, and he

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::14aae1a7c869f046db994a6d0241f388

Integer Programming Formulations and Cutting Plane Algorithms for the Maximum Selective Tree Problem

Autor: Onar, Ömer Burak, Ekim, Tınaz, Taşkın, Z. Caner

This paper considers the Maximum Selective Tree Problem (MSelTP) as a generalization of the Maximum Induced Tree problem. Given an undirected graph with a partition of its vertex set into clusters, MSelTP aims to choose the maximum number of vertices

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::87b4571bef4f659a56b2712c4bbe99e4

Flipper Games for Monadically Stable Graph Classes

Autor: Gajarský, Jakub, Mählmann, Nikolas, McCarty, Rose, Ohlmann, Pierre, Pilipczuk, Michał, Przybyszewski, Wojciech, Siebertz, Sebastian, Sokołowski, Marek, Toruńczyk, Szymon

A class of graphs C is monadically stable if for every unary expansion Ĉ of C, one cannot encode - using first-order transductions - arbitrarily long linear orders in graphs from C. It is known that nowhere dense graph classes are monadically stabl

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9a5d5c7dd0528de4b5872108bbe86adb