Source author record

César Hernández-Cruz

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

11works

2topics

4close 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.

preprint2022arXiv

Minimal obstructions for polarity, monopolarity, unipolarity and $(s,1)$ -polarity in generalizations of cographs

It is known that every hereditary property can be characterized by finitely many minimal obstructions when restricted to either the class of cographs or the class of $P_4$ -reducible graphs. In this work, we prove that also when restricted to the classes of $P_4$ -sparse graphs and $P_4$ -extendible graphs (both of which extend $P_4$ -reducible graphs) every hereditary property can be characterized by finitely many minimal obstructions. We present complete lists of $P_4$ -sparse and $P_4$ -extendible minimal obstructions for polarity, monopolarity, unipolarity, and $(s,1)$ -polarity, where $s$ is a positive integer. In parallel to the case of $P_4$ -reducible graphs, all the $P_4$ -sparse minimal obstructions for these hereditary properties are cographs.

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

preprint2020arXiv

Minimal obstructions for a matrix partition problem in chordal graphs

If $M$ is an $m \times m$ matrix over $\{ 0, 1, \ast \}$ , an $M$ -partition of a graph $G$ is a partition $(V_1, \dots V_m)$ such that $V_i$ is completely adjacent (non-adjacent) to $V_j$ if $M_{ij} = 1$ ( $M_{ij} = 0$ ), and there are no further restrictions between $V_i$ and $V_j$ if $M_{ij} = \ast$ . Having an $M$ -partition is a hereditary property, thus it can be characterized by a set of minimal obstructions (forbidden induced subgraphs minimal with the property of not having an $M$ -partition). It is known that for every $3 \times 3$ matrix $M$ over $\{ 0, 1, \ast \}$ , there are finitely many chordal minimal obstructions for the problem of determining whether a graph admits an $M$ -partition, except for two matrices, $M_1 = \left( \begin{array}{ccc} 0 & \ast & \ast \\ \ast & 0 & 1 \\ \ast & 1 & 0 \end{array} \right)$ and $M_2 = \left( \begin{array}{ccc} 0 & \ast & \ast \\ \ast & 0 & 1 \\ \ast & 1 & 1 \end{array} \right)$ . For these two matrices an infinite family of chordal minimal obstructions is known (the same family for both matrices), but the complete set of minimal obstructions is not. In this work we present the complete family of chordal minimal obstructions for $M_1$ .

preprint2020arXiv

Minimum Weighted Szeged Index Trees

Weighted Szeged index is a recently introduced extension of the well-known Szeged index. In this paper, we present a new tool to analyze and characterize minimum weighted Szeged index trees. We exhibit the best trees with up to 81 vertices and use this information, together with our results, to propose various conjectures on the structure of minimum weighted Szeged index trees.

preprint2016arXiv

A dichotomy for the kernel by $H$ -walks problem in digraphs

Let $H = (V_H, A_H)$ be a digraph which may contain loops, and let $D = (V_D, A_D)$ be a loopless digraph with a coloring of its arcs $c: A_D \to V_H$ . An $H$ -walk of $D$ is a walk $(v_0, \dots, v_n)$ of $D$ such that $(c(v_{i-1}, v_i), c(v_i, v_{i+1}))$ is an arc of $H$ , for every $1 \le i \le n-1$ . For $u, v \in V_D$ , we say that $u$ reaches $v$ by $H$ -walks if there exists an $H$ -walk from $u$ to $v$ in $D$ . A subset $S \subseteq V_D$ is a kernel by $H$ -walks of $D$ if every vertex in $V_D \setminus S$ reaches by $H$ -walks some vertex in $S$ , and no vertex in $S$ can reach another vertex in $S$ by $H$ -walks. A panchromatic pattern is a digraph $H$ such that every arc-colored digraph $D$ has a kernel by $H$ -walks. In this work, we prove that every digraph $H$ is either a panchromatic pattern, or the problem of determining whether an arc-colored digraph $D$ has a kernel by $H$ -walks is $NP$ -complete.

preprint2016arXiv

Minimal digraph obstructions for small matrices

Given a $\{ 0, 1, \ast \}$ -matrix $M$ , a minimal $M$ -obstruction is a digraph $D$ such that $D$ is not $M$ -partitionable, but every proper induced subdigraph of $D$ is. In this note we present a list of all the $M$ -obstructions for every $2 \times 2$ matrix $M$ . Notice that this note will be part of a larger paper, but we are archiving it now so we can cite the results.

preprint2016arXiv

On the existence of $3$ - and $4$ -kernels in digraphs

Let $D = (V(D), A(D))$ be a digraph. A subset $S \subseteq V(D)$ is $k$ -independent if the distance between every pair of vertices of $S$ is at least $k$ , and it is $\ell$ -absorbent if for every vertex $u$ in $V(D) \setminus S$ there exists $v \in S$ such that the distance from $u$ to $v$ is less than or equal to $\ell$ . A $k$ -kernel is a $k$ -independent and $(k-1)$ -absorbent set. A kernel is simply a $2$ -kernel. A classical result due to Duchet states that if every directed cycle in a digraph $D$ has at least one symmetric arc, then $D$ has a kernel. We propose a conjecture generalizing this result for $k$ -kernels and prove it true for $k = 3$ and $k = 4$ .

preprint2015arXiv

Colourings, Homomorphisms, and Partitions of Transitive Digraphs

We investigate the complexity of generalizations of colourings (acyclic colourings, $(k,\ell)$ -colourings, homomorphisms, and matrix partitions), for the class of transitive digraphs. Even though transitive digraphs are nicely structured, many problems are intractable, and their complexity turns out to be difficult to classify. We present some motivational results and several open problems.

preprint2013arXiv

Point determining digraphs, $\{0,1\}$ -matrix partitions, and dualities in full homomorphisms

We prove that every point-determining digraph $D$ contains a vertex $v$ such that $D-v$ is also point determining. We apply this result to show that for any $\{0,1\}$ -matrix $M$ , with $k$ diagonal zeros and $\ell$ diagonal ones, the size of a minimal $M$ -obstruction is at most $(k+1)(\ell+1)$ . This extends the results of Sumner, and of Feder and Hell, from undirected graphs and symmetric matrices to digraphs and general matrices.

preprint2012arXiv

On the existence and number of $(k+1)$ -kings in $k$ -quasi-transitive digraphs

Let $D=(V(D), A(D))$ be a digraph and $k \ge 2$ an integer. We say that $D$ is $k$ -quasi-transitive if for every directed path $(v_0, v_1,..., v_k)$ in $D$ , then $(v_0, v_k) \in A(D)$ or $(v_k, v_0) \in A(D)$ . Clearly, a 2-quasi-transitive digraph is a quasi-transitive digraph in the usual sense. Bang-Jensen and Gutin proved that a quasi-transitive digraph $D$ has a 3-king if and only if $D$ has a unique initial strong component and, if $D$ has a 3-king and the unique initial strong component of $D$ has at least three vertices, then $D$ has at least three 3-kings. In this paper we prove the following generalization: A $k$ -quasi-transitive digraph $D$ has a $(k+1)$ -king if and only if $D$ has a unique initial strong component, and if $D$ has a $(k+1)$ -king then, either all the vertices of the unique initial strong components are $(k+1)$ -kings or the number of $(k+1)$ -kings in $D$ is at least $(k+2)$ .

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.

César Hernández-Cruz

Research overview

Is this your work?

11 publications

Orientations without forbidden patterns on three vertices

Minimal obstructions for polarity, monopolarity, unipolarity and $(s,1)$ -polarity in generalizations of cographs

Duality pairs and homomorphisms to oriented and unoriented cycles

Minimal obstructions for a matrix partition problem in chordal graphs

Minimum Weighted Szeged Index Trees

A dichotomy for the kernel by $H$ -walks problem in digraphs

Minimal digraph obstructions for small matrices

On the existence of $3$ - and $4$ -kernels in digraphs

Colourings, Homomorphisms, and Partitions of Transitive Digraphs

Point determining digraphs, $\{0,1\}$ -matrix partitions, and dualities in full homomorphisms

On the existence and number of $(k+1)$ -kings in $k$ -quasi-transitive digraphs

See the researcher in context

Building this map preview

César Hernández-Cruz

Research overview

Is this your work?

11 publications

Orientations without forbidden patterns on three vertices

Minimal obstructions for polarity, monopolarity, unipolarity and (s,1)(s,1)(s,1)-polarity in generalizations of cographs

Duality pairs and homomorphisms to oriented and unoriented cycles

Minimal obstructions for a matrix partition problem in chordal graphs

Minimum Weighted Szeged Index Trees

A dichotomy for the kernel by HHH-walks problem in digraphs

Minimal digraph obstructions for small matrices

On the existence of 333- and 444-kernels in digraphs

Colourings, Homomorphisms, and Partitions of Transitive Digraphs

Point determining digraphs, {0,1}\{0,1\}{0,1}-matrix partitions, and dualities in full homomorphisms

On the existence and number of (k+1)(k+1)(k+1)-kings in kkk-quasi-transitive digraphs

See the researcher in context

Building this map preview

Minimal obstructions for polarity, monopolarity, unipolarity and $(s,1)$ -polarity in generalizations of cographs

A dichotomy for the kernel by $H$ -walks problem in digraphs

On the existence of $3$ - and $4$ -kernels in digraphs

Point determining digraphs, $\{0,1\}$ -matrix partitions, and dualities in full homomorphisms

On the existence and number of $(k+1)$ -kings in $k$ -quasi-transitive digraphs