Independent feedback vertex sets for graphs of bounded diameter

DOI10.1016/j.ipl.2017.11.004zbMath1422.68104arXiv1707.09383OpenAlexW2963110909MaRDI QIDQ1685021

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

Publication date: 13 December 2017

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1707.09383

zbMATH Keywords

computational complexitydiameterindependent feedback vertex setnear-bipartite graphs

Mathematics Subject Classification ID

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) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (14)

Partitioning \(H\)-free graphs of bounded diameter ⋮ Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity ⋮ Degree-constrained 2-partitions of graphs ⋮ Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration ⋮ Domination number and feedback vertex number of complements of line graphs ⋮ Partitioning \(P_4\)-tidy graphs into a stable set and a forest ⋮ 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 ⋮ Acyclic, star, and injective colouring: bounding the diameter ⋮ Feedback arc number and feedback vertex number of Cartesian product of directed cycles ⋮ Acyclic, star, and injective colouring: bounding the diameter ⋮ Recognizing Graphs Close to Bipartite Graphs ⋮ Faster 3-Coloring of Small-Diameter Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Algorithms and almost tight results for 3-colorability of small diameter graphs
• The complexity of surjective homomorphism problems-a survey
• On parameterized independent feedback vertex set
• The complexity of some problems related to GRAPH 3-COLORABILITY
• Vertex arboricity and maximum degree
• Three complexity results on coloring \(P_k\)-free graphs
• Cycle transversals in perfect graphs and cographs
• Partition the vertices of a graph into one independent set and one acyclic set
• Open Problems on Graph Coloring for Special Graph Classes
• Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set
• Recognizing Graphs Close to Bipartite Graphs
• Independent Feedback Vertex Set for P_5-free Graphs
• Partitioning a triangle-free planar graph into a forest and a forest of bounded degree

This page was built for publication: Independent feedback vertex sets for graphs of bounded diameter