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

DOI10.1016/j.disc.2005.09.016zbMath1093.05044OpenAlexW2068819940MaRDI QIDQ2497500

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

independent setacyclic setnear-bipartition

Mathematics Subject Classification ID

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

Related Items (15)

On equistable, split, CIS, and related classes of graphs ⋮ A note on orientation and chromatic number of graphs ⋮ Independent feedback vertex sets for graphs of bounded diameter ⋮ Partitions of hypergraphs under variable degeneracy constraints ⋮ Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration ⋮ 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 ⋮ The complexity of some acyclic improper colourings ⋮ Approximability of the independent feedback vertex set problem for bipartite graphs ⋮ Partitioning a graph into degenerate subgraphs ⋮ Acyclic, star, and injective colouring: bounding the diameter ⋮ Acyclic, star, and injective colouring: bounding the diameter ⋮ Recognizing Graphs Close to Bipartite Graphs ⋮ Independent Feedback Vertex Set for P_5-free Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some simplified NP-complete graph problems
• The complexity of some problems related to GRAPH 3-COLORABILITY
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• \(r\)-bounded \(k\)-complete bipartite bihypergraphs and generalized split graphs
• On the vertex arboricity of planar graphs of diameter two
• The point-arboricity of a graph

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