Source author record

Santiago Guzmán-Pro

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO

Catalog footprint

Research overview

2works

2topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Orientations without forbidden patterns on three vertices

Given a set $F$ of oriented graphs, a graph $G$ is an $F$ -graph if it admits an $F$ -free orientation. Building on previous work by Bang-Jensen and Urrutia, we propose a master algorithm that determines if a graph admits an $F$ -free orientation when $F$ is a subset of the orientations of $P_3$ and the transitive triangle. We extend previous results of Skrien by studying the class of $F$ -graphs, when $F$ is any set of oriented graphs of order three. Structural characterizations for all such sets are provided, except for the so-called perfectly-orientable graphs and one of its subclasses, which remain as open problems.

preprint2020arXiv

Duality pairs and homomorphisms to oriented and unoriented cycles

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. 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$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.