Solving partition problems with colour-bipartitions

DOI10.1007/s00373-012-1270-zzbMath1305.05187MaRDI QIDQ742575

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 algorithm; edge-coloured graphs; partition problems; monopolar graphs; unipolar graphs

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Unnamed Item, Solving Partition Problems Almost Always Requires Pushing Many Vertices Around, On the Polarity and Monopolarity of Graphs, Algorithms for unipolar and generalized split graphs, Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs, Recognition of unipolar and generalised split graphs, Partitioning a graph into disjoint cliques and a triangle-free graph, Monopolar graphs: complexity of computing classical graph parameters

Cites Work

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