Isometric path complexity of graphs

DOI10.1016/J.DISC.2025.114743MaRDI QIDQ6884410zbMATH OpenFDO

Authors Dibyayan Chakraborty, J. Chalopin, Florent Foucaud, Yann Vaxès

Publication date 15 December 2025

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DISC.2025.114743

zbMATH Keywords

hyperbolic graphsisometric path complexityisometric path coverouterstring graphsshortest pathsTruemper configurations

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Cites work

• \(k\)-chordal graphs: from cops and robber to compact routing via treewidth
• A decomposition theorem for partially ordered sets
• A game of cops and robbers
• An algorithm for the maximum weight independent set problem on outerstring graphs
• Asteroidal Triple-Free Graphs
• Circle graphs are quadratically χ‐bounded
• Complexity and algorithms for isometric path cover on chordal graphs and beyond
• Computing maximum independent set on outerstring graphs and their relatives
• Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
• Core congestion is inherent in hyperbolic networks
• Cycles and Connectivity in Graphs
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications
• Enumeration of Far-apart Pairs by Decreasing Distance for Faster Hyperbolicity Computation
• Fast approximation of eccentricities and distances in hyperbolic graphs
• Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm
• Graph classes with structured neighborhoods and algorithmic applications
• scientific article; zbMATH DE number 4031953 (Why is no real title available?)
• Hyperbolicity and chordality of a graph
• Intersection graphs of rays and grounded segments
• Isometric path complexity of graphs
• LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
• Mim-width. I. Induced path problems
• On the size of outer-string representations
• Outerstring graphs are -bounded
• String graphs. I: The number of critical nonstring graphs is infinite
• The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
• The strong perfect graph theorem
• The world of hereditary graph classes viewed through Truemper configurations
• Twin-width. I: Tractable FO model checking
• Universally signable graphs
• Wheel-free planar graphs

Cited in

(1)

• Covering and partitioning of split, chain and cographs with isometric paths

This page was built for publication: Isometric path complexity of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6884410)