Imagen de Portada

Non-crossing $H$-graphs: a generalization of proper interval graphs admitting FPT algorithms

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Bonomo-Braberman, Flavia, Brettell, Nick, Köhler, Noleen, Munaro, Andrea, Paulusma, Daniël
Formato:	Preprint
Publicado:	2025
Materias:	Computational Complexity Discrete Mathematics Combinatorics
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Solving Problems on Generalized Convex Graphs via Mim-Width
por: Bonomo-Braberman, Flavia, et al.
Publicado: (2020)

Comparing Width Parameters on Graph Classes
por: Brettell, Nick, et al.
Publicado: (2023)

Computing parameters that generalize interval graphs using restricted modular partitions
por: Bonomo-Braberman, Flavia, et al.
Publicado: (2025)

Computing Subset Vertex Covers in $H$-Free Graphs
por: Brettell, Nick, et al.
Publicado: (2023)

Trees with proper thinness 2
por: Bonomo-Braberman, Flavia, et al.
Publicado: (2025)

A Brooks-type theorem for the k-choosability of graphs with maximum local edge-connectivity k
por: Bastida, Sam, et al.
Publicado: (2026)

Graph Classes Closed under Self-intersection
por: Dabrowski, Konrad K., et al.
Publicado: (2025)

Non-empty intersection of longest paths in $H$-free graphs
por: Long Jr., James A., et al.
Publicado: (2023)

Complexity and algorithms for matching cut problems in graphs without long induced paths and cycles
por: Le, Hoang-Oanh, et al.
Publicado: (2023)

Finding d-Cuts in Claw-free Graphs
por: Ahn, Jungho, et al.
Publicado: (2025)

Dichotomies for Maximum Matching Cut: $H$-Freeness, Bounded Diameter, Bounded Radius
por: Lucke, Felicia, et al.
Publicado: (2023)

On the hull and interval numbers of oriented graphs
por: Araujo, J., et al.
Publicado: (2022)

Combinatorial refinement on circulant graphs
por: Kluge, Laurence
Publicado: (2022)

Finding d-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and H-Free Graphs
por: Lucke, Felicia, et al.
Publicado: (2024)

On full-separating sets and related codes in graphs
por: Chakraborty, Dipayan, et al.
Publicado: (2024)

Temporal Reachability Dominating Sets: contagion in temporal graphs
por: Kutner, David C., et al.
Publicado: (2023)

A structural description of Zykov and Blanche Descartes graphs
por: Marin, Malory, et al.
Publicado: (2024)

On the hardness of recognizing graphs of small mim-width and its variants
por: la Tour, Max Dupré, et al.
Publicado: (2025)

Complexity results for a cops and robber game on directed graphs
por: Ben-Ameur, Walid, et al.
Publicado: (2024)

Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification
por: Eagling-Vose, Tala, et al.
Publicado: (2025)

Finding $d$-Cuts in Probe $H$-Free Graphs
por: Dabrowski, Konrad K., et al.
Publicado: (2025)

Optimal b-Colourings and Fall Colourings in $H$-Free Graphs
por: Ahn, Jungho, et al.
Publicado: (2026)

Steiner Forest for $H$-Subgraph-Free Graphs
por: Eagling-Vose, Tala, et al.
Publicado: (2026)

Bounding Width on Graph Classes of Constant Diameter
por: Dabrowski, Konrad K., et al.
Publicado: (2025)

On the satisfiability of random $3$-SAT formulas with $k$-wise independent clauses
por: Caragiannis, Ioannis, et al.
Publicado: (2024)

Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-graphs
por: Lozin, Vadim, et al.
Publicado: (2022)

Clique-Width: Harnessing the Power of Atoms
por: Dabrowski, Konrad K., et al.
Publicado: (2020)

Weakly toll convexity and proper interval graphs
por: Dourado, Mitre C., et al.
Publicado: (2022)

Complexity of the (Connected) Cluster Vertex Deletion problem on $H$-free graphs
por: Le, Hoang-Oanh, et al.
Publicado: (2024)

Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions
por: Alecu, Bogdan, et al.
Publicado: (2024)

On algorithmic applications of sim-width and mim-width of $(H_1, H_2)$-free graphs
por: Munaro, Andrea, et al.
Publicado: (2022)

Isometric path complexity of graphs
por: Chakraborty, Dibyayan, et al.
Publicado: (2022)

Finding Minimum Matching Cuts in $H$-free Graphs
por: Lucke, Felicia, et al.
Publicado: (2025)

On graphs coverable by k shortest paths
por: Dumas, Maël, et al.
Publicado: (2022)

Adjacency labelling for proper minor-closed graph classes
por: Dujmović, Vida, et al.
Publicado: (2026)

Algorithms and complexity for monitoring edge-geodetic sets in graphs
por: Foucaud, Florent, et al.
Publicado: (2024)

CMSO-transducing tree-like graph decompositions
por: Campbell, Rutger, et al.
Publicado: (2024)

Removing bottlenecks in the recognition of small $(k,\ell)$-graph classes
por: Bonomo-Braberman, Flavia, et al.
Publicado: (2025)

Faster algorithms for graph homomorphism via tractable constraint satisfaction
por: Carbonnel, Clément
Publicado: (2026)

Thinness and its variations on some graph families and coloring graphs of bounded thinness
por: Bonomo-Braberman, Flavia, et al.
Publicado: (2023)