Convex partitions of graphs induced by paths of order three

zbMATH Open1280.68095MaRDI QIDQ5396751FDOQ5396751

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

Publication date: 3 February 2014

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

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

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)

Cited In (20)

• Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs
• Title not available (Why is that?)
• Complexity aspects of the triangle path convexity
• Poidge-convexity in triangular lattices
• On the Carathéodory number of interval and graph convexities
• On three polynomial kernels of sequences for arbitrarily partitionable graphs
• Carathéodory number of \(P_3\)-convexity of claw-free graphs
• Formulas in connection with parameters related to convexity of paths on three vertices: caterpillars and unit interval graphs
• The Carathéodory number of the \(P_3\) convexity of chordal 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
• A general framework for path convexities
• 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 Partitions of Graphs
• Covering graphs with convex sets and partitioning graphs 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)