Orientations without forbidden patterns on three vertices

DOI10.1016/J.AMC.2024.128912MaRDI QIDQ6994314zbMATH OpenFDO

Authors Santiago Guzmán-Pro, César Hernández-Cruz

Publication date 24 April 2025

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.AMC.2024.128912

zbMATH Keywords

\(\mathrm{Forb}_e (F)\)-graphforbidden subgraph characterizationgeneralized colouringgraph homomorphism

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75)

Cites work

• 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs
• \(1\)-perfectly orientable graphs and graph products
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
• An algorithm for fraternal orientation of graphs
• Decomposing and colouring some locally semicomplete digraphs
• Depth-First Search and Linear Graph Algorithms
• Digraphs
• Graph classes and forbidden patterns on three vertices
• Graph theory
• In-tournament digraphs
• Normal Helly circular-arc graphs and its subclasses
• On coloring digraphs with forbidden induced subgraphs
• Ordering without forbidden patterns
• Oriented expressions of graph properties
• Partial characterizations of 1-perfectly orientable graphs
• Restricted circular-arc graphs and clique cycles
• Sur le coloriage des graphs
• Trivially perfect graphs

This page was built for publication: Orientations without forbidden patterns on three vertices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6994314)