ﻻ يوجد ملخص باللغة العربية
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$. Ban and Linial conjectured that {em every bridgeless cubic graph admits a $2$--bisection except for the Petersen graph}. In this note, we prove Ban--Linials conjecture for claw--free cubic graphs.
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}
A cycle $C$ of length $k$ in graph $G$ is extendable if there is another cycle $C$ in $G$ with $V(C) subset V(C)$ and length $k+1$. A graph is cycle extendable if every non-Hamiltonian cycle is extendable. In 1990 Hendry conjectured that any Hamilton
A graph is strongly perfect if every induced subgraph H has a stable set that meets every maximal clique of H. A graph is claw-free if no vertex has three pairwise non-adjacent neighbors. The characterization of claw-free graphs that are strongly per
Resolving a conjecture of Furedi from 1988, we prove that with high probability, the random graph $G(n,1/2)$ admits a friendly bisection of its vertex set, i.e., a partition of its vertex set into two parts whose sizes differ by at most one in which
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