Describing hereditary properties by forbidden circular orderings

DOI10.1016/j.amc.2022.127555OpenAlexW3215650477MaRDI 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

zbMATH Keywords

graph classesforbidden subgraph characterizationsvertex orderings with forbidden patterns

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Complexity of computation (including implicit computational complexity) (03D15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

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

This page was built for publication: Describing hereditary properties by forbidden circular orderings