Recognizing Graphs Close to Bipartite Graphs

DOI10.4230/LIPIcs.MFCS.2017.70zbMath1441.68167OpenAlexW2726678275MaRDI QIDQ5111287

Matthew Johnson, Carl Feghali, Daniël Paulusma, Konrad K. Dabrowski, Marthe Bonamy

Publication date: 26 May 2020

Full work available at URL: https://hal.science/hal-02527078

zbMATH Keywords

degenerate graphsreconfiguration graphsnear-bipartite graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Independent feedback vertex sets for graphs of bounded diameter ⋮ Degree-constrained 2-partitions of graphs ⋮ Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration ⋮ Unnamed Item ⋮ Sparse Graphs Are Near-Bipartite ⋮ Independent feedback vertex set for \(P_5\)-free graphs ⋮ Approximability of the independent feedback vertex set problem for bipartite graphs ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ Introduction to reconfiguration ⋮ Independent Feedback Vertex Set for P_5-free Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms and almost tight results for 3-colorability of small diameter graphs
• Finding shortest paths between graph colourings
• On parameterized independent feedback vertex set
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Brooks' graph-coloring theorem and the independence number
• Some simplified NP-complete graph problems
• The complexity of some problems related to GRAPH 3-COLORABILITY
• On \(P_4\)-transversals of perfect graphs
• Independent feedback vertex sets for graphs of bounded diameter
• Recognition of unipolar and generalised split graphs
• Partitioning sparse graphs into an independent set and a forest of bounded degree
• Vertex arboricity and maximum degree
• Threshold graphs and related topics
• Cycle transversals in perfect graphs and cographs
• Stable-\(\Pi\) partitions of graphs
• Partition the vertices of a graph into one independent set and one acyclic set
• Bisplit graphs
• A Reconfigurations Analogue of Brooks' Theorem and Its Consequences
• Deterministic Algorithms for the Independent Feedback Vertex Set Problem
• Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
• On the computational complexity of (O,P)-partition problems
• List Partitions
• A generalization of perfect graphs?i-perfect graphs
• Vertex partitions and maximum degenerate subgraphs
• Between 2- and 3-colorability

This page was built for publication: Recognizing Graphs Close to Bipartite Graphs