Partitioning P₄-tidy graphs into a stable set and a forest

DOI10.1016/J.DAM.2023.05.016MaRDI QIDQ6166038zbMATH OpenOpenAlexWikidataFDO

Authors Raquel S. F. Bravo, Rodolfo A. Oliveira, Fábio Nunes da Silva, Uéverton S. Souza

Publication date 2 August 2023

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2023.05.016

zbMATH Keywords

partitionstable setacyclic setnear-bipartite\(P_4\)-tidy

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Theory of computing (68Qxx) Graph theory (05Cxx)

Recommendations

• Partition the vertices of a graph into one independent set and one acyclic set
• scientific article; zbMATH DE number 1263950
• Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs
• Planar graphs without short even cycles are near-bipartite

Cites work

• scientific article; zbMATH DE number 991436 (Why is no real title available?)
• scientific article; zbMATH DE number 1375569 (Why is no real title available?)
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• A New Class of Brittle Graphs
• A graph coloring algorithm for large scheduling problems
• Automata, Languages and Programming
• Complement reducible graphs
• Cycle transversals in perfect graphs and cographs
• Deadlock resolution in wait-for graphs by vertex/arc deletion
• Graph partitioning applied to the logic testing of combinational circuits
• Impact of minimum-cut density-balanced partitioning solutions in distributed webpage ranking
• Independent feedback vertex set for \(P_5\)-free graphs
• Independent feedback vertex sets for graphs of bounded diameter
• On a unique tree representation for \(P_ 4\)-extendible graphs
• On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
• On graphs with limited number of \(P_{4}\)-partners
• P-Components and the Homogeneous Decomposition of Graphs
• Partition the vertices of a graph into one independent set and one acyclic set
• Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
• VLSI physical design. From graph partitioning to timing closure

Cited in

(2)

• Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs
• Near-bipartiteness, connected near-bipartiteness, independent feedback vertex set and acyclic vertex cover on graphs having small dominating sets

This page was built for publication: Partitioning \(P_4\)-tidy graphs into a stable set and a forest

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166038)