Cover Image

A quasi-optimal upper bound for induced paths in sparse graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Couëtoux, Basile, Defrain, Oscar, Raymond, Jean-Florent
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

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

Long induced paths and forbidden patterns: Polylogarithmic bounds
by: Duron, Julien, et al.
Published: (2024)

Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly
by: Beaudou, Laurent, et al.
Published: (2021)

Parameterized complexity of isometric path partition: treewidth and diameter
by: Chakraborty, Dibyayan, et al.
Published: (2025)

Local certification of geometric graph classes
by: Defrain, Oscar, et al.
Published: (2023)

Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets
by: Bonamy, Marthe, et al.
Published: (2020)

Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
by: Beaudou, Laurent, et al.
Published: (2025)

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

Linear colorings of graphs
by: Hilaire, Claire, et al.
Published: (2025)

On locating and neighbor-locating colorings of sparse graphs
by: Chakraborty, Dipayan, et al.
Published: (2023)

Translating between the representations of an acyclic convex geometry of bounded degree
by: Defrain, Oscar, et al.
Published: (2025)

Weakly-sparse and strongly flip-flat classes of graphs are uniformly almost-wide
by: Ghasemi, Fatemeh, et al.
Published: (2025)

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

Enumerating minimal solution sets for metric graph problems
by: Bergougnoux, Benjamin, et al.
Published: (2023)

Enumerating minimal dominating sets and variants in chordal bipartite graphs
by: Castelo, Emanuel, et al.
Published: (2025)

Generating minimal redundant and maximal irredundant sets in incidence graphs
by: Castelo, Emanuel, et al.
Published: (2026)

On cuts of small chromatic number in sparse graphs
by: Aubian, Guillaume, et al.
Published: (2025)

Characterizing optimal monitoring edge-geodetic sets for some structured graph classes
by: Foucaud, Florent, 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)

Equitable coloring of sparse graphs
by: Liu, Weichan, et al.
Published: (2024)

A Caro-Wei bound for induced linear forests in graphs
by: Joret, Gwenaël, et al.
Published: (2024)

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

Canonical labelling of sparse random graphs
by: Verbitsky, Oleg, et al.
Published: (2024)

Twin-width of sparse random graphs
by: Hendrey, Kevin, et al.
Published: (2023)

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

An optimal chromatic bound for ($P_2+P_3$, gem)-free graphs
by: Char, Arnab, et al.
Published: (2024)

Sample compression schemes for balls in structurally sparse graphs
by: Bourneuf, Romain, et al.
Published: (2026)

Hypergraph dualization with FPT-delay parameterized by the degeneracy and dimension
by: Bartier, Valentin, 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)

Strengthening the Murty-Simon conjecture on diameter 2 critical graphs
by: Dailly, Antoine, et al.
Published: (2018)

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

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

Hitting all longest paths in $H$-free graphs and $H$-graphs
by: de Lima, Paloma T., et al.
Published: (2025)

A quasi-polynomial bound for the minimal excluded minors for a surface
by: Houdaigoui, Sarah, et al.
Published: (2025)

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

On the enumeration of signatures of XOR-CNF's
by: Creignou, Nadia, et al.
Published: (2024)

Bounds and extremal graphs for monitoring edge-geodetic sets in graphs
by: Foucaud, Florent, et al.
Published: (2024)

On three domination-based identification problems in block graphs
by: Chakraborty, Dipayan, et al.
Published: (2018)

On near optimal colorable graphs
by: Angeliya, C. U., et al.
Published: (2025)

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