Convex partitions of graphs induced by paths of order three

MaRDI QIDQ5396751zbMATH OpenFDO

Authors C. C. Centeno, Simone Dantas, Mitre C. Dourado, Dieter Rautenbach, Jayme L. Szwarcfiter

Publication date 3 February 2014

Full work available at URL https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1519/0.html

zbMATH Keywords

graph convexityconvex partition

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Partitioning a graph into convex sets
• Convex Partitions of Graphs
• Convex \(p\)-partitions of bipartite graphs
• On nontrivial covers and partitions of graphs by convex sets
• Covering graphs with convex sets and partitioning graphs into convex sets

Cited in

(21)

• Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs
• scientific article; zbMATH DE number 6823372 (Why is no real title available?)
• Complexity aspects of the triangle path convexity
• On the Carathéodory number of interval and graph convexities
• Poidge-convexity in triangular lattices
• On three polynomial kernels of sequences for arbitrarily partitionable graphs
• Carathéodory number of \(P_3\)-convexity of claw-free graphs
• The Carathéodory number of the \(P_3\) convexity of chordal graphs
• Formulas in connection with parameters related to convexity of paths on three vertices: caterpillars and unit interval graphs
• On the \(P_3\)-hull number of some products of graphs
• On the \(P_3\)-hull number of Kneser graphs
• On the \(P_3\)-hull number of Hamming graphs
• On the Carathéodory number for the convexity of paths of order three
• Graphs with few \(P_4\)'s under the convexity of paths of order three
• Inapproximability results for graph convexity parameters
• Bootstrap percolation in strong products of graphs
• Convex \(p\)-partitions of bipartite graphs
• Covering graphs with convex sets and partitioning graphs into convex sets
• Convex Partitions of Graphs
• Partitioning a graph into convex sets
• Domination and convexity problems in the target set selection model

This page was built for publication: Convex partitions of graphs induced by paths of order three

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