Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
From MaRDI portal
Publication:6056774
DOI10.1002/jgt.22683zbMath1522.05362arXiv1707.09817OpenAlexW3164327262MaRDI QIDQ6056774
Marthe Bonamy, Carl Feghali, Matthew Johnson, Konrad K. Dabrowski, Daniël Paulusma
Publication date: 4 October 2023
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1707.09817
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (3)
Partitioning into degenerate graphs in linear time ⋮ Partitioning \(P_4\)-tidy graphs into a stable set and a forest ⋮ On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding shortest paths between graph colourings
- On parameterized independent feedback vertex set
- Decomposing a planar graph of girth 5 into an independent set and a forest
- 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
- Efficient edge domination problems in graphs
- On \(P_4\)-transversals of perfect graphs
- Independent feedback vertex sets for graphs of bounded diameter
- Recognition of unipolar and generalised split graphs
- Independent feedback vertex set for \(P_5\)-free graphs
- Decomposing a planar graph into an independent set and a 3-degenerate graph
- Vertex arboricity and maximum degree
- Threshold graphs and related topics
- Decomposing a planar graph into degenerate graphs
- Cycle transversals in perfect graphs and cographs
- Variable degeneracy: Extensions of Brooks' and Gallai's theorems
- Stable-\(\Pi\) partitions of graphs
- Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
- Partition the vertices of a graph into one independent set and one acyclic set
- A characterization of perfect graphs
- Bisplit graphs
- A Reconfigurations Analogue of Brooks' Theorem and Its Consequences
- The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
- On the computational complexity of (O,P)-partition problems
- List Partitions
- Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set
- A generalization of perfect graphs?i-perfect graphs
- Recognizing Graphs Close to Bipartite Graphs
- Vertex partitions and maximum degenerate subgraphs
- The Point-Arboricity of Planar Graphs
- Partitioning a triangle-free planar graph into a forest and a forest of bounded degree
- Between 2- and 3-colorability
- Minimal reducible bounds for the class of \(k\)-degenerate graphs
This page was built for publication: Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
