Cover Image

Hitting all longest paths in $H$-free graphs and $H$-graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	de Lima, Paloma T., Nikabadi, Amir, Rzążewski, Paweł
Format:	Preprint
Published:	2025
Subjects:	Combinatorics Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Equitable coloring of large bipartite graphs
by: Nikabadi, Amir
Published: (2026)

Maximum list $r$-colorable induced subgraphs in $kP_3$-free graphs
by: Galby, Esther, et al.
Published: (2025)

Clique-width and induced topological minors
by: Bieliński, Paweł Rafał, et al.
Published: (2026)

A polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number
by: Pilipczuk, Marcin, et al.
Published: (2023)

List coloring ordered graphs with forbidden induced subgraphs
by: Piecyk, Marta, et al.
Published: (2025)

Polynomial-time recognition and maximum independent set in Burling graphs
by: Rzążewski, Paweł, et al.
Published: (2024)

Non-empty intersection of longest paths in $P_5$-free and claw-free graphs
by: Lima, Paloma T., et al.
Published: (2024)

Tree-independence number of $P_5$-free graphs with no large bicliques
by: Blažej, Václav, et al.
Published: (2026)

Constant congestion brambles in directed graphs
by: Masařík, Tomáš, et al.
Published: (2021)

Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
by: Majewski, Konrad, et al.
Published: (2022)

Tight bound on treedepth in terms of pathwidth and longest path
by: Hatzel, Meike, et al.
Published: (2023)

Burling graphs in graphs with large chromatic number
by: Abrishami, Tara, et al.
Published: (2025)

Induced matching treewidth and tree-independence number, revisited
by: Alon, Noga, et al.
Published: (2025)

Ramsey Goodness of paths and unbalanced graphs
by: Botler, Fábio, et al.
Published: (2024)

Long induced paths in sparse graphs and graphs with forbidden patterns
by: Duron, Julien, et al.
Published: (2024)

On graphs coverable by chubby shortest paths
by: Hatzel, Meike, et al.
Published: (2025)

Vertex-critical graphs in co-gem-free graphs
by: Beaton, Iain, et al.
Published: (2024)

Strong isometric path complexity of graphs: Asymptotic minors, restricted holes, and graph operations
by: Chakraborty, Dibyayan, et al.
Published: (2025)

The sandwich problem for odd-hole-free and even-hole-free graphs
by: Cameron, Kathie, et al.
Published: (2024)

Path eccentricity of $k$-AT-free graphs and application on graphs with the consecutive ones property
by: Bastide, Paul, et al.
Published: (2024)

$θ$-free matching covered graphs
by: Joshi, Rohinee, et al.
Published: (2024)

Coloring bridge-free antiprismatic graphs
by: Robin, Cléophée, et al.
Published: (2024)

Playing Sudoku on random 3-regular graphs
by: Dippel, Jack, et al.
Published: (2025)

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

Nucleation-free independent graphs with implied nonedges
by: Cheng, Jialong, et al.
Published: (2025)

Secure domination in $P_5$-free graphs
by: Gupta, Uttam K., et al.
Published: (2025)

Independent sets and colorings of $K_{t,t,t}$-free graphs
by: Dhawan, Abhishek, et al.
Published: (2025)

Proper conflict-free choosability of planar graphs
by: Wang, Yuting, et al.
Published: (2025)

Computing fixed point free automorphisms of graphs
by: Abiad, Aida, et al.
Published: (2026)

The strong chromatic index of $K_{t,t}$-free graphs
by: Bi, Richard, et al.
Published: (2026)

A quasi-optimal upper bound for induced paths in sparse graphs
by: Couëtoux, Basile, et al.
Published: (2025)

On coarse tree decompositions and coarse balanced separators
by: Abrishami, Tara, et al.
Published: (2025)

Distance-based (and path-based) covering problems for graphs of given cyclomatic number
by: Chakraborty, Dibyayan, et al.
Published: (2025)

Planar induced paths via a decomposition into non-crossing ordered graphs
by: Duron, Julien, et al.
Published: (2025)

A polynomial bound on the pathwidth of graphs edge-coverable by $k$ shortest paths
by: Baste, Julien, et al.
Published: (2025)

Hamiltonian path and Hamiltonian cycle are solvable in polynomial time in graphs of bounded independence number
by: Jedličková, Nikola, et al.
Published: (2023)

$K_{2,3}$-induced minor-free graphs admit quasi-isometry with additive distortion to graphs of tree-width at most two
by: Chakraborty, Dibyayan
Published: (2025)

Non-crossing $H$-graphs: a generalization of proper interval graphs admitting FPT algorithms
by: Bonomo-Braberman, Flavia, et al.
Published: (2025)

Canonical labelling of random regular graphs
by: Isaev, Mikhail, et al.
Published: (2026)