Recognizing Graphs Close to Bipartite Graphs
From MaRDI portal
Publication:5111287
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Recommendations
Cites work
- scientific article; zbMATH DE number 3882470 (Why is no real title available?)
- scientific article; zbMATH DE number 3503283 (Why is no real title available?)
- scientific article; zbMATH DE number 1263950 (Why is no real title available?)
- A generalization of perfect graphs?i-perfect graphs
- A reconfigurations analogue of Brooks' theorem and its consequences
- Algorithms and almost tight results for 3-colorability of small diameter graphs
- Between 2- and 3-colorability
- Bisplit graphs
- Brooks' graph-coloring theorem and the independence number
- Cycle transversals in perfect graphs and cographs
- Deterministic Algorithms for the Independent Feedback Vertex Set Problem
- Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Finding shortest paths between graph colourings
- Independent feedback vertex sets for graphs of bounded diameter
- List Partitions
- On \(P_4\)-transversals of perfect graphs
- On parameterized independent feedback vertex set
- On the computational complexity of (O,P)-partition problems
- Partition the vertices of a graph into one independent set and one acyclic set
- Partitioning sparse graphs into an independent set and a forest of bounded degree
- Recognition of unipolar and generalised split graphs
- Some simplified NP-complete graph problems
- Stable-\(\Pi\) partitions of graphs
- The complexity of some problems related to GRAPH 3-COLORABILITY
- Threshold graphs and related topics
- Vertex arboricity and maximum degree
- Vertex partitions and maximum degenerate subgraphs
Cited in
(15)- Independent feedback vertex sets for graphs of bounded diameter
- Using contracted solution graphs for solving reconfiguration problems
- Coloring problems on bipartite graphs of small diameter
- Degree-constrained 2-partitions of graphs
- A linear time algorithm for determining almost bipartite graphs
- Near-bipartiteness, connected near-bipartiteness, independent feedback vertex set and acyclic vertex cover on graphs having small dominating sets
- Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
- Partition the vertices of a graph into one independent set and one acyclic set
- Independent Feedback Vertex Set for P_5-free Graphs
- Sparse graphs are near-bipartite
- Introduction to reconfiguration
- Independent feedback vertex set for \(P_5\)-free graphs
- scientific article; zbMATH DE number 7378380 (Why is no real title available?)
- Approximability of the independent feedback vertex set problem for bipartite graphs
- Recognition of overlap graphs
This page was built for publication: Recognizing Graphs Close to Bipartite Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111287)
