Solving partition problems with colour-bipartitions

DOI10.1007/S00373-012-1270-ZzbMATH Open1305.05187OpenAlexW1982050567MaRDI QIDQ742575FDOQ742575

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Complexity of Timetable and Multicommodity Flow Problems
• Transitiv orientierbare Graphen
• On Injective Colourings of Chordal Graphs
• About recognizing (\(\alpha\) ,\(\beta\) ) classes of polar graphs
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
• Line-Polar Graphs: Characterization and Recognition
• Polar Permutation Graphs
• List monopolar partitions of claw-free graphs
• On the Polarity and Monopolarity of Graphs
• Polar cographs
• Recognizing line-polar bipartite graphs in time \(O(n)\)
• A forbidden subgraph characterization of line-polar bipartite graphs
• An efficiently solvable graph partition problem to which many problems are reducible
• Recognizing Polar Planar Graphs Using New Results for Monopolarity

Cited In (10)

• Solving Partition Problems Almost Always Requires Pushing Many Vertices Around
• A partition problem on colored sets
• Partitioning a graph into disjoint cliques and a triangle-free graph
• On the Polarity and Monopolarity of Graphs
• Recognition of unipolar and generalised split graphs
• Title not available (Why is that?)
• Algorithms for unipolar and generalized split graphs
• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
• Monopolar graphs: complexity of computing classical graph parameters
• Recent Advances in Constraints

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)