Solving partition problems with colour-bipartitions

DOI10.1007/S00373-012-1270-ZMaRDI QIDQ742575zbMATH OpenOpenAlexFDO

Authors Ross Churchley, Jing Huang

Publication date 19 September 2014

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00373-012-1270-z

zbMATH Keywords

polynomial algorithmpartition problemsedge-coloured graphsmonopolar graphsunipolar graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• On the Polarity and Monopolarity of Graphs
• Complexity and algorithms for recognizing polar and monopolar graphs
• Polar permutation graphs
• List monopolar partitions of claw-free graphs
• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs

Cites work

• scientific article; zbMATH DE number 3977053 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• A forbidden subgraph characterization of line-polar bipartite graphs
• About recognizing (\(\alpha\) ,\(\beta\) ) classes of polar graphs
• An efficiently solvable graph partition problem to which many problems are reducible
• Homomorphism duality in edge-coloured graphs
• Line-Polar Graphs: Characterization and Recognition
• List monopolar partitions of claw-free graphs
• On Injective Colourings of Chordal Graphs
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the Polarity and Monopolarity of Graphs
• Polar cographs
• Polar permutation graphs
• Recognizing line-polar bipartite graphs in time \(O(n)\)
• Recognizing polar planar graphs using new results for monopolarity
• Transitiv orientierbare Graphen
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard

Cited in

(13)

• Recognition of unipolar and generalised split graphs
• Algorithms for unipolar and generalized split graphs
• On the Polarity and Monopolarity of Graphs
• Solving partition problems almost always requires pushing many vertices around
• Monopolar graphs: complexity of computing classical graph parameters
• List monopolar partitions of claw-free graphs
• scientific article; zbMATH DE number 7378721 (Why is no real title available?)
• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
• A partition problem on colored sets
• Uniquely monopolar-partitionable block graphs
• Partitioning a graph into disjoint cliques and a triangle-free graph
• Recent Advances in Constraints
• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs

This page was built for publication: Solving partition problems with colour-bipartitions

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