Báo cáo viên: Đoàn Duy Trung (ĐHBK Hà nội và postdoc Viện Toán học)
Thời gian: Thứ 5, ngày 25/06/2020. 9h30.
Địa điểm: Phòng 612, nhà A6, Viện Toán học.
Tóm tắt: A path in a vertex-coloured graph is called emph{conflict-free} if there is a colour used on exactly one of its vertices. A vertex-coloured graph is said to be emph{conflict-free vertex-connected} if any two distinct vertices of the graph are connected by a conflict-free vertex-path. The emph{conflict-free vertex-connection number}, denoted by $vcfc(G)$, is the smallest number of colours needed in order to make $G$ conflict-free vertex-connected. Clearly, $vcfc(G) geq 2$ for every connected graph on $n geq 2$ vertices.Our main result of this paper is the following: Let $G$ be a connected graph of order $n$. If $|E(G)|geq{n-6choose 2} +7$, then $vcfc(G)leq3$. We also show that $vcfc(G)leq k+3-t$ for every connected graph $G$ with $k$ cut-vertices and $t$ being the maximum number of cut-vertices belonging to a block of $G.$. |
