Duality pairs and homomorphisms to oriented and unoriented cycles

DOI10.37236/9747MaRDI QIDQ2048544zbMATH OpenOpenAlexFDO

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

Publication date 6 August 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2003.05605

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

oriented pathundirected cycle

Mathematics Subject Classification ID

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)

Abstract: In the homomorphism order of digraphs, a duality pair is an ordered pair of digraphs $(G,H)$ such that for any digraph, $D$, $GoD$ if and only if $DotoH$. The directed path on $k+1$ vertices together with the transitive tournament on $k$ vertices is a classic example of a duality pair. This relation between paths and tournaments implies that a graph is $k$-colourable if and only if it admits an orientation with no directed path on more than $k$-vertices. In this work, for every undirected cycle $C$ we find an orientation $C_D$ and an oriented path $P_C$, such that $(P_C,C_D)$ is a duality pair. As a consequence we obtain that there is a finite set, $F_C$, such that an undirected graph is homomorphic to $C$, if and only if it admits an $F_C$-free orientation. As a byproduct of the proposed duality pairs, we show that if $T$ is a tree of height at most $3$, one can choose a dual of $T$ of linear size with respect to the size of $T$.

Review text

Summary: In the homomorphism order of digraphs, a duality pair is an ordered pair of digraphs \((G,H)\) such that for any digraph, \(D\), \(G\to D\) if and only if \(D\not \to H\). The directed path on \(k+1\) vertices together with the transitive tournament on \(k\) vertices is a classic example of a duality pair. In this work, for every undirected cycle \(C\) we find an orientation \(C_D\) and an oriented path \(P_C\), such that \((P_C,C_D)\) is a duality pair. As a consequence we obtain that there is a finite set, \(F_C\), such that an undirected graph is homomorphic to \(C\), if and only if it admits an \(F_C\)-free orientation. As a byproduct of the proposed duality pairs, we show that if \(T\) is an oriented tree of height at most \(3\), one can choose a dual of \(T\) of linear size with respect to the size of \(T\).

Recommendations

• Homomorphisms to oriented paths
• On maximal finite antichains in the homomorphism order of directed graphs
• scientific article; zbMATH DE number 2061631
• The Existence of Homomorphisms to Oriented Cycles
• Homomorphisms to oriented cycles

Cites work

• A dualistic approach to bounding the chromatic number of a graph
• A Polynomial Algorithm for Homomorphisms to Oriented Cycles
• A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
• Duality theorems for finite structures (characterising gaps and good characterisations)
• Homomorphisms to oriented cycles
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 3205929 (Why is no real title available?)
• scientific article; zbMATH DE number 3257176 (Why is no real title available?)
• Images of rigid digraphs
• Incidence matrices and interval graphs
• Nombre chromatique et plus longs chemins d'un graphe
• On multiplicative graphs and the product conjecture
• On unavoidable digraphs in orientations of graphs
• Short Answers to Exponentially Long Questions: Extremal Aspects of Homomorphism Duality
• The Existence of Homomorphisms to Oriented Cycles
• Zur algebraischen Begründung der Graphentheorie. I

Cited in

(7)

• Homomorphisms to oriented paths
• Oriented expressions of graph properties
• Adjoint functors and tree duality
• scientific article; zbMATH DE number 2061631 (Why is no real title available?)
• Edge-coloured graph homomorphisms, paths, and duality
• No finite-infinite antichain duality in the homomorphism poset of directed graphs
• The duality index of oriented regular hypermaps

This page was built for publication: Duality pairs and homomorphisms to oriented and unoriented cycles

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