Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
Open Access
- 24 May 2021
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 98 (1) , 81-109
Abstract
No abstract availableKeywords
All Related Versions
Funding Information
- Leverhulme Trust (RPG‐2016‐258)
- London Mathematical Society (41536)
- Engineering and Physical Sciences Research Council (EP/K025090/1)
This publication has 33 references indexed in Scilit:
- Finding Paths between graph colourings: PSPACE-completeness and superpolynomial distancesTheoretical Computer Science, 2009
- Vertex partitions and maximum degenerate subgraphsJournal of Graph Theory, 2007
- Bisplit graphsDiscrete Mathematics, 2005
- Minimal reducible bounds for the class of k-degenerate graphsDiscrete Mathematics, 2001
- Variable degeneracy: extensions of Brooks’ and Gallai's theoremsDiscrete Mathematics, 2000
- On the computational complexity of (O,P)-partition problemsDiscussiones Mathematicae Graph Theory, 1997
- Efficient edge domination problems in graphsInformation Processing Letters, 1993
- Some simplified NP-complete graph problemsTheoretical Computer Science, 1976
- The Point-Arboricity of Planar GraphsJournal of the London Mathematical Society, 1969
- On colouring the nodes of a networkMathematical Proceedings of the Cambridge Philosophical Society, 1941