关键词: 色数, $b$-色数, 导出子图, interlacing图

Abstract: Graph coloring is one of the most hot issues in graph theory and has important applications in many fields. For a connected graph $G$, we use $\chi(G)$ and $\varphi (G)$ to denote the chromatic number and $b$-chromatic number of $G$, respectively. Let $R,S$ be two connected graphs. Then $G$ is said to be $\{R, S\}$-free if $G$ does not contain $R$ and $S$ as induced subgraphs. In this paper, we prove that for any connected graphs $R$ and $S$ of order at least 4, every connected (2-edge-connected or 2-connected) $\{R, S\}$-free graph $G$ implies $\chi(G)=\varphi (G)$ if and only if $\{R, S\}\preceq\{P_5, Z_1\}$, where $P_5$ is a path of order 5 and $Z_1$ is the graph obtained by identifying one vertex of $P_2$ and one vertex of a triangle. Besides, we give the lower bound of $b$-chromatic numbers of two special classes of interlacing graphs $IG_{n, 2}$ and $IG_{n, 3}$.

Key words: chromatic number, $b$-chromatic number, induced subgraph, interlacing graph