On graphs that are not PCGs
From MaRDI portal
Publication:2512661
DOI10.1016/j.tcs.2015.01.011zbMath1306.05085MaRDI QIDQ2512661
Debajyoti Mondal, Md. Saidur Rahman, Stephane Durocher
Publication date: 30 January 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2015.01.011
Related Items
Characterizing star-PCGs, A Necessary Condition and a Sufficient Condition for Pairwise Compatibility Graphs, On the enumeration of minimal non-pairwise compatibility graphs, Some classes of graphs that are not PCGs, Some reduction operations to pairwise compatibility graphs, Pairwise compatibility graphs: complete characterization for wheels, Multi-interval Pairwise Compatibility Graphs, Pairwise Compatibility Graphs: A Survey
Cites Work
- Strictly chordal graphs are leaf powers
- Rooted directed path graphs are leaf powers
- Characterising \((k,\ell )\)-leaf powers
- Exact leaf powers
- Pairwise compatibility graphs
- On pairwise compatibility graphs having Dilworth number \(k\)
- On pairwise compatibility graphs having Dilworth number two
- On Graph Powers for Leaf-Labeled Trees
- On Relaxing the Constraints in Pairwise Compatibility Graphs
- DISCOVERING PAIRWISE COMPATIBILITY GRAPHS
- Leaf Powers and Their Properties: Using the Trees
- Triangle-Free Outerplanar 3-Graphs are Pairwise Compatibility Graphs
- On Graphs That Are Not PCGs
- The complexity of satisfiability problems
- On Dilworth k Graphs and Their Pairwise Compatibility