Stable-\(\Pi\) partitions of graphs

DOI10.1016/j.dam.2013.07.001zbMath1306.05189OpenAlexW1973061987MaRDI QIDQ2255049

Vadim V. Lozin, Juraj Stacho, Konrad K. Dabrowski

Publication date: 6 February 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.07.001

zbMATH Keywords

NP-completenesspolynomial timehereditary propertyfactorial propertyspeed of graph propertystable-\(\Pi\) partition

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration ⋮ Recognizing Graphs Close to Bipartite Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the computational complexity of graph vertex partition
• On \(P_4\)-transversals of chordal graphs
• Partitioning graphs into complete and empty graphs
• Some simplified NP-complete graph problems
• The complexity of some problems related to GRAPH 3-COLORABILITY
• Efficient edge domination problems in graphs
• On \(P_4\)-transversals of perfect graphs
• The NP-completeness of (1,r)-subcolorability of cubic graphs
• Partitioning chordal graphs into independent sets and cliques
• The speed of hereditary properties of graphs
• Threshold graphs and related topics
• Partitioning cographs into cliques and stable sets
• Bisplit graphs
• Node-Deletion Problems on Bipartite Graphs
• On the computational complexity of (O,P)-partition problems
• List Partitions
• A generalization of perfect graphs?i-perfect graphs
• Between 2- and 3-colorability