Cover Image

Perfect Edge Domination in $P_6$-free Graphs and in Graphs Without Efficient Edge Dominating Sets

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Grippo, Luciano N., Lin, Min Chih, Vera, Camilo
Format:	Preprint
Published:	2025
Subjects:	Combinatorics 05C70, 05C85, 05A99 68R10, 68Q25
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Graphs whose vertices of degree at least 2 lie in a triangle
by: Forte, Vinicius L. do, et al.
Published: (2022)

Edge open packing: complexity, algorithmic aspects, and bounds
by: Brešar, Boštjan, et al.
Published: (2024)

The Mutual-Visibility Problem In Directed Graphs
by: Stojanović, Vanja
Published: (2026)

Three results towards the approximation of special maximum matchings in graphs
by: Mkrtchyan, Vahan
Published: (2024)

Perfecting the Line Graph
by: Bal, Hartosh Singh
Published: (2025)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
by: Abdullah, Duaa, et al.
Published: (2025)

On Edge-Disjoint Maximal Outerplanar Graphs
by: Okada, Yuto, et al.
Published: (2026)

$(t,r)$ Broadcast Domination Numbers and Densities of the Truncated Square Tiling Graph
by: Cervantes, Jillian, et al.
Published: (2024)

Catching Rats in $H$-minor-free Graphs
by: Gorsky, Maximilian, et al.
Published: (2025)

On the Complexity of Bipartite Degree Realizability
by: Miklós, István
Published: (2025)

An NP-hardness result for the colored constrained maximum 2-edge-colorable subgraph problem in bipartite graphs
by: Mkrtchyan, Vahan
Published: (2024)

Structure and algorithms for graphs excluding grids with small parity breaks as odd-minors
by: Gollin, J. Pascal, et al.
Published: (2023)

Lower General Position Sets in Graphs
by: Di Stefano, Gabriele, et al.
Published: (2023)

Integral Biflow Maximization
by: Ding, Guoli, et al.
Published: (2024)

Tree decompositions meet induced matchings: beyond Max Weight Independent Set
by: Lima, Paloma T., et al.
Published: (2024)

Minimal obstructions to $C_5$-coloring in hereditary graph classes
by: Goedgebeur, Jan, et al.
Published: (2024)

A Linear Kernel for Independent Set Reconfiguration in Planar Graphs
by: Bousquet, Nicolas, et al.
Published: (2025)

Tight complexity bounds for diagram commutativity verification
by: Malko, Artem, et al.
Published: (2025)

A Note on Graph Burning of Path Forests
by: Tan, Ta Sheng, et al.
Published: (2023)

Zero-free regions of partition functions with applications to algorithms and graph limits
by: Regts, Guus
Published: (2015)

VC-dimension of subsets of Hamming graphs
by: Housholder, Christopher, et al.
Published: (2025)

Cup Stacking in Graphs
by: Fay, Paul, et al.
Published: (2023)

Lower Bounds for the Pfaffian Number of Graphs
by: Junchaya, Enrique, et al.
Published: (2026)

Limiting Behavior of Resistances in Triangular Graphs
by: Hendel, Russell Jay
Published: (2021)

Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs
by: Furmańczyk, Hanna, et al.
Published: (2020)

A dichotomy theorem on the complexity of 3-uniform hypergraphic degree sequence graphicality
by: Logsdon, Sara, et al.
Published: (2024)

The zero blocking numbers of grid graphs
by: Lin, Hau-Yi, et al.
Published: (2025)

Zero blocking numbers of graphs with complexity results
by: Lin, Hau-Yi, et al.
Published: (2025)

Quota Trees
by: White, Tad
Published: (2024)

Reconstructing a graph from the distance matrix of its boundary
by: Cáceres, José, et al.
Published: (2024)

The zero blocking numbers of generalized Kneser graphs and generalized Johnson graphs
by: Lin, Hau-Yi, et al.
Published: (2025)

W-state graphs: Structure and Algorithms
by: Gajjala, Rishikesh, et al.
Published: (2026)

Irreversible $k$-Threshold Dynamics on Corona and Base-$b$ Corona Product Graphs
by: Moon, Eric J., et al.
Published: (2025)

Refutation of Spectral Graph Theory Conjectures with Search Algorithms)
by: Roucairol, Milo, et al.
Published: (2024)

Approximating branchwidth on parametric extensions of planarity
by: Thilikos, Dimitrios M., et al.
Published: (2023)

The Upper Clique Transversal Problem
by: Milanič, Martin, et al.
Published: (2023)

A $5/4$-Approximation for Two-Edge Connectivity
by: Bosch-Calvo, Miguel, et al.
Published: (2024)

Algorithmic releases on the spanning trees of suitable graphs
by: Imbesi, Maurizio, et al.
Published: (2017)

Extremal Trees With Prescribed Burning Numbers
by: Leong, Eugene Jun Tong, et al.
Published: (2025)

Odd Cycle Transversal on $P_5$-free Graphs in Polynomial Time
by: Agrawal, Akanksha, et al.
Published: (2024)