Recognizing Graphs Close to Bipartite Graphs
DOI10.4230/LIPICS.MFCS.2017.70zbMATH Open1441.68167OpenAlexW2726678275MaRDI QIDQ5111287FDOQ5111287
Matthew Johnson, Carl Feghali, Daniël Paulusma, Konrad Dabrowski, Marthe Bonamy
Publication date: 26 May 2020
Full work available at URL: https://hal.science/hal-02527078
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)
Cites Work
- Brooks' graph-coloring theorem and the independence number
- Threshold graphs and related topics
- Algorithms and almost tight results for 3-colorability of small diameter graphs
- Title not available (Why is that?)
- On parameterized independent feedback vertex set
- Some simplified NP-complete graph problems
- Title not available (Why is that?)
- Cycle transversals in perfect graphs and cographs
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Finding shortest paths between graph colourings
- List Partitions
- The complexity of some problems related to GRAPH 3-COLORABILITY
- Partition the vertices of a graph into one independent set and one acyclic set
- Bisplit graphs
- Recognition of unipolar and generalised split graphs
- Title not available (Why is that?)
- Vertex arboricity and maximum degree
- On the computational complexity of (O,P)-partition problems
- On \(P_4\)-transversals of perfect graphs
- Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
- Independent feedback vertex sets for graphs of bounded diameter
- Partitioning sparse graphs into an independent set and a forest of bounded degree
- A generalization of perfect graphs?i-perfect graphs
- Stable-\(\Pi\) partitions of graphs
- A reconfigurations analogue of Brooks' theorem and its consequences
- Deterministic Algorithms for the Independent Feedback Vertex Set Problem
- Vertex partitions and maximum degenerate subgraphs
- Between 2- and 3-colorability
Cited In (12)
- Approximability of the independent feedback vertex set problem for bipartite graphs
- Using contracted solution graphs for solving reconfiguration problems
- Recognition of overlap graphs
- Independent feedback vertex set for \(P_5\)-free graphs
- Independent feedback vertex sets for graphs of bounded diameter
- Near-bipartiteness, connected near-bipartiteness, independent feedback vertex set and acyclic vertex cover on graphs having small dominating sets
- Independent Feedback Vertex Set for P_5-free Graphs
- Degree-constrained 2-partitions of graphs
- Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
- Introduction to reconfiguration
- Sparse Graphs Are Near-Bipartite
- Title not available (Why is that?)
Recommendations
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)
