Partition the vertices of a graph into one independent set and one acyclic set

DOI10.1016/J.DISC.2005.09.016MaRDI QIDQ2497500zbMATH OpenOpenAlexFDO

Authors Jinjiang Yuan, Aifeng Yang

Publication date 4 August 2006

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2005.09.016

zbMATH Keywords

acyclic setindependent setnear-bipartition

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

Recommendations

• Independent feedback vertex sets for graphs of bounded diameter
• Recognizing Graphs Close to Bipartite Graphs
• Partitions of graphs into one or two independent sets and cliques
• scientific article; zbMATH DE number 1263950
• Planar graphs without short even cycles are near-bipartite

Cites work

• \(r\)-bounded \(k\)-complete bipartite bihypergraphs and generalized split graphs
• Graph theory
• scientific article; zbMATH DE number 3503283 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1263950 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• On the vertex arboricity of planar graphs of diameter two
• Some simplified NP-complete graph problems
• The complexity of some problems related to GRAPH 3-COLORABILITY
• The point-arboricity of a graph

Cited in

(19)

• Independent feedback vertex sets for graphs of bounded diameter
• Independent feedback vertex set for P₅-free graphs
• Partitioning a graph into degenerate subgraphs
• A note on orientation and chromatic number of graphs
• On equistable, split, CIS, and related classes of graphs
• Recognizing Graphs Close to Bipartite Graphs
• Sparse graphs are near-bipartite
• Independent Feedback Vertex Set for P₅-free Graphs
• The complexity of some acyclic improper colourings
• Acyclic, star, and injective colouring: bounding the diameter
• Approximability of the independent feedback vertex set problem for bipartite graphs
• Acyclic, star, and injective colouring: bounding the diameter
• Partitions of hypergraphs under variable degeneracy constraints
• Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
• Partitioning P₄-tidy graphs into a stable set and a forest
• Sparsity in covering solutions
• Near-bipartiteness, connected near-bipartiteness, independent feedback vertex set and acyclic vertex cover on graphs having small dominating sets
• Complexity of near-3-choosability problem
• Near-bipartiteness on graphs having small dominating sets

This page was built for publication: Partition the vertices of a graph into one independent set and one acyclic set

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