Star Partitions of Perfect Graphs
DOI10.1007/978-3-662-43948-7_15zbMath1409.68148arXiv1402.2589OpenAlexW2145610052MaRDI QIDQ5167740
Laurent Bulteau, Jiehua Chen, Robert Bredereck, Vincent Froese, Rolf Niedermeier, René van Bevern, Gerhard J. Woeginger
Publication date: 1 July 2014
Published in: Journal of Graph Theory, Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1402.2589
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17)
Related Items (11)
Cites Work
- Unnamed Item
- The weak 3-flow conjecture and the weak circular flow conjecture
- Combinatorial and computational aspects of graph packing and graph decomposition
- Nowhere-zero 3-flows and modulo \(k\)-orientations
- Interval scheduling and colorful independent sets
- NP-completeness results for some problems on subclasses of bipartite and chordal graphs
- A linear time recognition algorithm for proper interval graphs
- On the complexity of partitioning graphs into connected subgraphs
- Rectilinear planar layouts and bipolar orientations of planar graphs
- General factors of graphs
- Bipartite permutation graphs
- NP-completeness of graph decomposition problems
- \(k\)-path partitions in trees
- Matching and multidimensional matching in chordal and strongly chordal graphs
- On the \(k\)-path partition of graphs.
- Approximation algorithms for the test cover problem
- Algorithmic graph theory and perfect graphs
- Quasi-threshold graphs
- Partition into triangles on bounded degree graphs
- Packing bipartite graphs with covers of complete bipartite graphs
- The path partition problem and related problems in bipartite graphs
- On the Complexity of General Graph Factor Problems
- The LBFS Structure and Recognition of Interval Graphs
- Generalized planar matching
- Interval scheduling: A survey
- A Linear Recognition Algorithm for Cographs
- Planar 3DM is NP-complete
- Linear-time computability of combinatorial problems on series-parallel graphs
- Graph Classes: A Survey
- Network-Based Vertex Dissolution
This page was built for publication: Star Partitions of Perfect Graphs