Describing hereditary properties by forbidden circular orderings
From MaRDI portal
Publication:2096309
DOI10.1016/j.amc.2022.127555MaRDI QIDQ2096309
César Hernández-Cruz, Santiago Guzmán-Pro, Pavol Hell
Publication date: 16 November 2022
Published in: Applied Mathematics and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2112.00154
68R10: Graph theory (including graph drawing) in computer science
05C75: Structural characterization of families of graphs
03D15: Complexity of computation (including implicit computational complexity)
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graphs whose every independent set has a common neighbour
- Cyclic ordering is NP-complete
- Trivially perfect graphs
- Ordering without Forbidden Patterns
- On the complexity of the circular chromatic number
- On the Structure of Dense Triangle-Free Graphs
- Acyclic graph coloring and the complexity of the star chromatic number
- Characterizing circular-arc graphs
- Graph Classes and Forbidden Patterns on Three Vertices