ﻻ يوجد ملخص باللغة العربية
Motivated by analogous questions in the setting of Steiner triple systems and Latin squares, Nenadov, Sudakov and Wagner [Completion and deficiency problems, Journal of Combinatorial Theory Series B, 2020] recently introduced the notion of graph deficiency. Given a global spanning property $mathcal P$ and a graph $G$, the deficiency $text{def}(G)$ of the graph $G$ with respect to the property $mathcal P$ is the smallest non-negative integer $t$ such that the join $G*K_t$ has property $mathcal P$. In particular, Nenadov, Sudakov and Wagner raised the question of determining how many edges an $n$-vertex graph $G$ needs to ensure $G*K_t$ contains a $K_r$-factor (for any fixed $rgeq 3$). In this paper we resolve their problem fully. We also give an analogous result which forces $G*K_t$ to contain any fixed bipartite $(n+t)$-vertex graph of bounded degree and small bandwidth.
An edge-coloring of a graph $G$ with colors $1,ldots,t$ is an emph{interval $t$-coloring} if all colors are used, and the colors of edges incident to each vertex of $G$ are distinct and form an integer interval. It is well-known that there are graphs
A emph{proper $t$-edge-coloring} of a graph $G$ is a mapping $alpha: E(G)rightarrow {1,ldots,t}$ such that all colors are used, and $alpha(e) eq alpha(e^{prime})$ for every pair of adjacent edges $e,e^{prime}in E(G)$. If $alpha $ is a proper edge-col
A proper edge coloring of a graph $G$ with colors $1,2,dots,t$ is called a cyclic interval $t$-coloring if for each vertex $v$ of $G$ the edges incident to $v$ are colored by consecutive colors, under the condition that color $1$ is considered as con
The general position number of a graph $G$ is the size of the largest set of vertices $S$ such that no geodesic of $G$ contains more than two elements of $S$. The monophonic position number of a graph is defined similarly, but with `induced path in p
We consider homomorphisms of signed graphs from a computational perspective. In particular, we study the list homomorphism problem seeking a homomorphism of an input signed graph $(G,sigma)$, equipped with lists $L(v) subseteq V(H), v in V(G)$, of al