Complete partitions of graphs
DOI10.1007/S00493-007-2169-9zbMATH Open1164.68038OpenAlexW3138200510MaRDI QIDQ949754FDOQ949754
Authors: Magnús M. Halldórsson, Guy Kortsarz, Sivaramakrishnan Sivasubramanian, Jaikumar Radhakrishnan 
Publication date: 21 October 2008
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00493-007-2169-9
Recommendations
- Complete partitions of graphs
- Partition of a graph with its complete sub-graphs
- Partitions of Graphs
- Distinguishing partitions of complete multipartite graphs
- scientific article
- Partitioning graphs into complete and empty graphs
- Covering the complete graph by partitions
- scientific article; zbMATH DE number 3867385
- On partition graphs
- scientific article; zbMATH DE number 3970800
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- A threshold of ln n for approximating set cover
- Title not available (Why is that?)
- Hadwiger's conjecture is true for almost every graph
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Proof verification and the hardness of approximation problems
- Title not available (Why is that?)
- Polylogarithmic inapproximability
- Some optimal inapproximability results
- Approximating the minimum maximal independence number
- Hadwiger's conjecture for \(K_ 6\)-free graphs
- Approximating theDomatic Number
- Balls and bins: A study in negative dependence
- On the hardness of approximating minimization problems
- The complexity of harmonious colouring for trees
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Parallel Repetition Theorem
- The achromatic number of bounded degree trees
- Achromatic number is NP-complete for cographs and interval graphs
- Achromatic numbers of random graphs
- On the pseudoachromatic number of a graph
- Title not available (Why is that?)
- On approximating the achromatic number
- Approximating the achromatic number problem on bipartite graphs
- Complete partitions of graphs
- On the hardness of approximating spanners
- On the pseudoachromatic number of join of graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Partition graphs and coloring numbers of a graph
- Achromatic number versus pseudoachromatic number: A counterexample to a conjecture of Hedetniemi
- Asymmetric \(k\)-center is \(\log{^*}{n}\)-hard to approximate
Cited In (18)
- Approximability of Packing Disjoint Cycles
- Complete multipartite graphs and Braess edges
- Partitioning complete graphs by heterochromatic trees
- Title not available (Why is that?)
- Approximability of packing disjoint cycles
- Title not available (Why is that?)
- Title not available (Why is that?)
- Complete partitions of graphs
- Partition of a graph with its complete sub-graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Canonical Vertex Partitions
- Partitioning graphs into complete and empty graphs
- Title not available (Why is that?)
- Complete subgraphs in multipartite graphs
- The saturation function of complete partite graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
This page was built for publication: Complete partitions of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q949754)
