Disjoint clique cutsets in graphs without long holes

DOI10.1002/jgt.20057zbMath1061.05067OpenAlexW2527693017MaRDI QIDQ4676589

Elaine M. Eschen, R. Sritharan, Mark D. T. Petrick, Chính T. Hoàng

Publication date: 4 May 2005

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.20057

zbMATH Keywords

holesdecompositionperfect graphsrecognition algorithmcoloring algorithmbiclique separable graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Perfect graphs (05C17)

Related Items

Requiring chords in cycles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• Topics on perfect graphs
• Weakly triangulated graphs
• The strong perfect graph theorem
• Matrix multiplication via arithmetic progressions
• Decomposition by clique separators
• Star-cutsets and perfect graphs
• Coloring graphs with stable cutsets
• Finding large holes
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• The connectivity of minimal imperfect graphs

This page was built for publication: Disjoint clique cutsets in graphs without long holes