Cover Image

A polynomial bound on the pathwidth of graphs edge-coverable by $k$ shortest paths

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Baste, Julien, De Meyer, Lucas, Giocanti, Ugo, Objois, Etienne, Picavet, Timothé
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

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

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

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

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

Basis Number of Graphs Excluding Minors
by: Geniet, Colin, et al.
Published: (2026)

The treewidth and pathwidth of graph unions
by: Alecu, Bogdan, et al.
Published: (2022)

Tree-partitions of graphs with given pathwidth
by: Wood, David R.
Published: (2026)

Largest planar graphs of diameter $3$ and fixed maximum degree -- connection with fractional matchings
by: Dailly, Antoine, 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)

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)

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

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

Bounded twin-width graphs are polynomially $χ$-bounded
by: Bourneuf, Romain, et al.
Published: (2023)

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

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

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

A note on the structure of locally finite planar quasi-transitive graphs
by: Giocanti, Ugo
Published: (2024)

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)

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

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

Beyond recognizing well-covered graphs
by: Feghali, Carl, et al.
Published: (2024)

On universal graphs for trees and treewidth $k$ graphs
by: Kaul, Neel, et al.
Published: (2025)

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

Vertex-edge domination on subclasses of bipartite graphs
by: Pandey, Arti, et al.
Published: (2025)

On the expressive power of $2$-edge-colourings of graphs
by: Bok, Jan, et al.
Published: (2025)

Restricted subgraphs of edge-colored graphs and applications
by: Sudakov, Benny
Published: (2024)

Extremal minimal bipartite matching covered graphs
by: Mallik, Amit Kumar, 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 polynomial bound for the minimal excluded minors for a surface
by: Houdaigoui, Sarah, et al.
Published: (2026)

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

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

Large induced subgraph with a given pathwidth in outerplanar graphs
by: Matsumoto, Naoki, et al.
Published: (2025)

Separating the edges of a graph by cycles and by subdivisions of $K_4$
by: Botler, Fábio, et al.
Published: (2024)

Filling some gaps on the edge coloring problem of split graphs
by: Couto, Fernanda, et al.
Published: (2024)

Minimum number of arcs in $k$-critical digraphs with order at most $2k-1$
by: Picasarri-Arrieta, Lucas, et al.
Published: (2023)

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

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

Induced Disjoint Paths Without an Induced Minor
by: Aboulker, Pierre, et al.
Published: (2025)