Imagen de Portada

Extended formulations for induced tree and path polytopes of chordal graphs

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Dupont-Bouillard, Alexandre
Formato:	Preprint
Publicado:	2025
Materias:	Discrete Mathematics
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

A column generation algorithm for finding co-3-plexes in chordal graphs
por: Dupont-Bouillard, Alexandre
Publicado: (2026)

Extended formulations for the maximum weighted co-2-plex problem
por: Dupont-Bouillard, Alexandre, et al.
Publicado: (2025)

Contractions in perfect graph
por: Dupont-Bouillard, Alexandre, et al.
Publicado: (2024)

Extended formulations for the multilinear polytope of acyclic hypergraphs
por: Del Pia, Alberto, et al.
Publicado: (2025)

Backbone colouring of chordal graphs
por: Araújo, Júlio, et al.
Publicado: (2025)

Dichromatic number of chordal graphs
por: Bessy, Stéphane, et al.
Publicado: (2023)

Tree-layout based graph classes: proper chordal graphs
por: Paul, Christophe, et al.
Publicado: (2022)

Edge open packing on subclasses of chordal graphs
por: Santra, Kamal
Publicado: (2025)

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

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

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

On minimally tough chordal graphs
por: Dallard, Clément, et al.
Publicado: (2022)

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

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

The pseudo-Boolean polytope and polynomial-size extended formulations for binary polynomial optimization
por: Del Pia, Alberto, et al.
Publicado: (2023)

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

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

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

Recognition of chordal graphs and cographs which are Cover-Incomparability graphs
por: Anil, Arun, et al.
Publicado: (2023)

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

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

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

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

On the edge expansion of random polytopes
por: Ferber, Asaf, et al.
Publicado: (2025)

Lower bounds for dominating set reconfiguration on sparse (directed) graphs
por: Dirks, Jona, et al.
Publicado: (2025)

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

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

Complexity and algorithms for matching cut problems in graphs without long induced paths and cycles
por: Le, Hoang-Oanh, et al.
Publicado: (2023)

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

Blow-up structure of graphs excluding a tree or an apex-tree as a minor
por: Claus, Quentin, et al.
Publicado: (2026)

Listing spanning trees of outerplanar graphs by pivot-exchanges
por: Behrooznia, Nastaran, et al.
Publicado: (2024)

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

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

A note on the exact partition polytope of Frieze and Teng
por: Narayanan, Krishna, et al.
Publicado: (2026)

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

On the Virtual Network Embedding polytope
por: Benhamiche, Amal, et al.
Publicado: (2026)

Elimination distance to bounded degree on planar graphs
por: Lindermayr, Alexander, et al.
Publicado: (2020)

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

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

Generation of weighted trees, block trees and block graphs
por: Ekim, Tınaz, et al.
Publicado: (2024)