Duality pairs and homomorphisms to oriented and unoriented cycles

Abstract: In the homomorphism order of digraphs, a duality pair is an ordered pair of digraphs

(G, H)

such that for any digraph,

D

,

G o D

if and only if

D o t o H

. 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

.

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

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

Recommendations

Cites Work

Cited In (7)

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