Cover Image

Long induced paths and forbidden patterns: Polylogarithmic bounds

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Duron, Julien, Esperet, Louis, Raymond, Jean-Florent
Format:	Preprint
Published:	2024
Subjects:	Discrete Mathematics Combinatorics
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)

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

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

Cops and robber in graphs with bounded vertex cover number
by: Bose, Prosenjit, et al.
Published: (2026)

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

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

On the minimum number of inversions to make a digraph $k$-(arc-)strong
by: Duron, Julien, et al.
Published: (2023)

Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
by: Beaudou, Laurent, 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)

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

Nowhere-zero flow reconfiguration
by: Esperet, Louis, et al.
Published: (2025)

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

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

On the finiteness of $k$-vertex-critical $2P_2$-free graphs with forbidden induced squids or bulls
by: Adekanye, Melvin, et al.
Published: (2024)

Edge densities of drawings of graphs with one forbidden cell
by: Hahn, Benedikt, et al.
Published: (2025)

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

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

The structure of quasi-transitive graphs avoiding a minor with applications to the domino problem
by: Esperet, Louis, et al.
Published: (2023)

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

Grand zigzag knight's paths
by: Baril, Jean-Luc, et al.
Published: (2024)

A lattice on Dyck paths close to the Tamari lattice
by: Baril, Jean-Luc, et al.
Published: (2023)

Reductions in local certification
by: Esperet, Louis, et al.
Published: (2025)

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

Extremal digraphs for open neighbourhood location-domination and identifying codes
by: Foucaud, Florent, et al.
Published: (2023)

Algorithms and hardness for Metric Dimension on digraphs
by: Dailly, Antoine, et al.
Published: (2023)

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

Characterizing optimal monitoring edge-geodetic sets for some structured graph classes
by: Foucaud, Florent, et al.
Published: (2025)

Moderately beyond clique-width: reduced component max-leaf and related parameters
by: Bonnet, Édouard, et al.
Published: (2026)

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

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

Algorithms and complexity for path covers of temporal DAGs: when is Dilworth dynamic?
by: Chakraborty, Dibyayan, et al.
Published: (2024)

Interval H-graphs : Recognition and forbidden obstructions
by: Müller, Haiko, et al.
Published: (2025)

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

Orthogonality between acyclic subdigraphs and paths in digraphs
by: Silva, Caroline A. de Paula, et al.
Published: (2026)

Bipartite Turán number of paths and other trees
by: Bonamy, Marthe, et al.
Published: (2025)

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

Relation between broadcast domination and multipacking numbers on chordal and other hyperbolic graphs
by: Das, Sandip, et al.
Published: (2023)

Emerging consecutive pattern avoidance
by: Hassler, Nathanaël, et al.
Published: (2025)

Upper bounds on minimum size of feedback arc set of directed multigraphs with bounded degree
by: Gutin, Gregory, et al.
Published: (2024)

Half-integral Erdős-Pósa property for non-null $S$-$T$ paths
by: Chekan, Vera, et al.
Published: (2024)