Preprint

Characterization of graphs $G$ where $G \in \mathrm{obs}^*(H)$ for some graph $H$

Z. Rahimi M. H. Shirdareh-Haghighi Asma Namazi Department of Mathematics C. Science S. University Shiraz Iran

Aug 2026 · 0 citations · 8 references

Mathematics

Abstract

A full-homomorphism from a graph $G$ to a graph $H$ is a function on vertex sets that preserves adjacency and non-adjacency of vertices. A graph $G$ is called a minimal $H$-obstruction if it has no full-homomorphism to $H$ but every proper vertex induced subgraph of $G$ does. Such graphs can have at most $|V(H)|+1$ vertices. The set of minimal $H$-obstructions on $|V(H)|+1$ vertices is denoted by $\mathrm{obs*}(H)$. In question 2 of the paper"Santiago Guzm{\'a}n-Pro, Full-homomorphisms to paths and cycles, Discrete Mathematics, 347(3):113800, 2024"it is asked if there is a characterization of those graphs $G$ that lie in $\mathrm{obs*}(H)$ for some graph $H$. In this paper, we give a complete answer to this question.

arXiv Semantic Scholar

View source

Similar papers

Preprint Aug 2026

A dichotomy for the number of vertex-critical ($P_5$, $H$)-free graphs when $H$ is bipartite

A graph $G$ is $k$-vertex-critical if $\chi(G)=k$, but $\chi(H)<k$ for every induced subgraph $H$ of $G$. A graph $G$ is $(H_1,H_2,\dots,H_m)$-free if does not contain $H_i$ as an induced subgraph for any $i\in\{1,2,\dots,m\}$.We provide the following dichotomy that for bipartite graphs $H$ and any fixed integer $k\ge...

Iain Beaton, Ben Cameron · 1 citation

Preprint Aug 2026

Product structure of graphs excluding a topological minor

We prove that, for all positive integers $h$ and $t$ and every graph $X$ with $\mathrm{td}(X) \leq h$, there exists a positive integer $c(X,t)$ such that every graph $G$ with $\mathrm{tw}(G)<t$ that excludes $X$ as a topological minor is isomorphic to a subgraph of $H \boxtimes K_{c(X,t)}$ for some graph $H$ with $\mat...

Jędrzej Hodor, La Hoang, P. Micek et al. · 0 citations

Preprint Sep 2026

Alon's Question on Connectivity Graph-Codes: $f(d)=2^d$ for Every $d\geq 4$

For a finite graph $H$, a connectivity graph-code is a family $\mathcal C\subseteq 2^{E(H)}$ such that $A\triangle B$ is a connected spanning subgraph of $H$ whenever $A$ and $B$ are distinct members of $\mathcal C$. Let $m(H)$ denote the maximum size of such a family, and let $f(d)$ be the largest integer $q$ for whic...

Chen-Xiao Tian · 0 citations

Preprint Sep 2026

The strong (non-induced) Tur\'an numbers

In this paper we introduce and explore the following new graph invariant: For a graph $G$ on $k$ vertices, $G \neq K_k$, let $st(n,G)$ denote the maximum number of edges in a graph of order $n$ which does not contain any subgraph on $k$ vertices strictly containing $G$. A basic relation to classical Tur\'an numbers is...

Y. Caro, Z. Tuza · 0 citations

Preprint Aug 2026

Full homomorphisms to graph classes

Given a family of graphs $\mathcal{F}$, we define a graph $G$ to be fully $\mathcal{F}$-colourable if $G$ admits a full homomorphism to some $F$ in $\mathcal{F}$. We approach the problem of determining when a graph is fully $\mathcal{F}$-colourable in terms of minimal forbidden induced subgraphs. We provide general res...

P. Hell, César Hernández-Cruz · 0 citations

Preprint Sep 2026

Almost perfect graph classes

A graph $G$ is perfect if $\omega(H) = \chi(H)$ for each induced subgraph $H$ of $G$. In 2002, Chudnovsky, Robertson, Seymour, and Thomas famously proved the Strong Perfect Graph Theorem. Motivated by this forbidden induced subgraph characterization of the class of perfect graphs as well as the possible extension of ef...

Cicely Henderson, Hidde Koerts, Taite LaGrange et al. · 0 citations