Source author record

Mario Valencia-Pabon

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

3works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On restricted completions of chordal and trivially perfect graphs

Let $G$ be a graph having a vertex $v$ such that $H = G - v$ is a trivially perfect graph. We give a polynomial-time algorithm for the problem of deciding whether it is possible to add at most $k$ edges to $G$ to obtain a trivially perfect graph. This is a slight variation of the well-studied {\sc Edge Completion}, also known as {\sc Minimum Fill-In}, problem. We also show that if $H$ is a chordal graph, then the problem of deciding whether it is possible to add at most $k$ edges to $G$ to obtain a chordal graph is \NP-complete.

preprint2022arXiv

On the diameter of Schrijver graphs

For $k \geq 1$ and $n \geq 2k$ , the well known Kneser graph $\operatorname{KG}(n,k)$ has all $k$ -element subsets of an $n$ -element set as vertices; two such subsets are adjacent if they are disjoint. Schrijver constructed a vertex-critical subgraph $\operatorname{SG}(n,k)$ of $\operatorname{KG}(n,k)$ with the same chromatic number. In this paper, we compute the diameter of the graph $\operatorname{SG}(2k+r,k)$ with $r \geq 1$ . We obtain an exact value of the diameter of $\operatorname{SG}(2k+r,k)$ when $r \in \{1,2\}$ or when $r \geq k-3$ . For the remained cases, when $3 \leq r \leq k-4$ , we obtain that the diameter of $\operatorname{SG}(2k+r,k)$ belongs to the integer interval $[4..k-r-1]$ .

preprint2016arXiv

Shifts of the Stable Kneser Graphs and Hom-Idempotence

A graph $G$ is said to be {\em hom-idempotent} if there is a homomorphism from $G^2$ to $G$ , and {\em weakly hom-idempotent} if for some $n \geq 1$ there is a homomorphism from $G^{n+1}$ to $G^n$ . Larose et al. [{\em Eur. J. Comb. 19:867-881, 1998}] proved that Kneser graphs $\operatorname{KG}(n,k)$ are not weakly hom-idempotent for $n \geq 2k+1$ , $k\geq 2$ . For $s \geq 2$ , we characterize all the shifts (i.e., automorphisms of the graph that map every vertex to one of its neighbors) of $s$ -stable Kneser graphs $\operatorname{KG}(n,k)_{s-\operatorname{stab}}$ and we show that $2$ -stable Kneser graphs are not weakly hom-idempotent, for $n \geq 2k+2$ , $k \geq 2$ . Moreover, for $s,k\geq 2$ , we prove that $s$ -stable Kneser graphs $\operatorname{KG}(ks+1,k)_{s-\operatorname{stab}}$ are circulant graphs and so hom-idempotent graphs. Finally, for $s \geq 3$ , we show that $s$ -stable Kneser graphs $\operatorname{KG}(2s+2,2)_{s-\operatorname{stab}}$ are cores, not $χ$ -critical, not hom-idempotent and their chromatic number is equal to $s+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.