ﻻ يوجد ملخص باللغة العربية
Let $Oct_{1}^{+}$ and $Oct_{2}^{+}$ be the planar and non-planar graphs that obtained from the Octahedron by 3-splitting a vertex respectively. For $Oct_{1}^{+}$, we prove that a 4-connected graph is $Oct_{1}^{+}$-free if and only if it is $C_{6}^{2}$, $C_{2k+1}^{2}$ $(k geq 2)$ or it is obtained from $C_{5}^{2}$ by repeatedly 4-splitting vertices. We also show that a planar graph is $Oct_{1}^{+}$-free if and only if it is constructed by repeatedly taking 0-, 1-, 2-sums starting from ${K_{1}, K_{2} ,K_{3}} cup mathscr{K} cup {Oct,L_{5} }$, where $mathscr{K}$ is the set of graphs obtained by repeatedly taking the special 3-sums of $K_{4}$. For $Oct_{2}^{+}$, we prove that a 4-connected graph is $Oct_{2}^{+}$-free if and only if it is planar, $C_{2k+1}^{2}$ $(k geq 2)$, $L(K_{3,3})$ or it is obtained from $C_{5}^{2}$ by repeatedly 4-splitting vertices.
A emph{$k$--bisection} of a bridgeless cubic graph $G$ is a $2$--colouring of its vertex set such that the colour classes have the same cardinality and all connected components in the two subgraphs induced by the colour classes have order at most $k$
The 1-2-3 Conjecture, posed by Karo{n}ski, {L}uczak and Thomason, asked whether every connected graph $G$ different from $K_2$ can be 3-edge-weighted so that every two adjacent vertices of $G$ get distinct sums of incident weights. The 1-2 Conjecture
Given two graphs $H_1$ and $H_2$, a graph $G$ is $(H_1,H_2)$-free if it contains no induced subgraph isomorphic to $H_1$ or $H_2$. Let $P_t$ be the path on $t$ vertices. A graph $G$ is $k$-vertex-critical if $G$ has chromatic number $k$ but every pro
The ErdH{o}s-Simonovits stability theorem states that for all epsilon >0 there exists alpha >0 such that if G is a K_{r+1}-free graph on n vertices with e(G) > ex(n,K_{r+1}) - alpha n^2, then one can remove epsilon n^2 edges from G to obtain an r-par
A vertex of a graph is bisimplicial if the set of its neighbors is the union of two cliques; a graph is quasi-line if every vertex is bisimplicial. A recent result of Chudnovsky and Seymour asserts that every non-empty even-hole-free graph has a bisi