×

The chromatic number of graphs without certain induced subgraphs. (English) Zbl 1349.05129

Summary: According to Gyárfás’ conjecture that for a given forest \(F\), there exists an integer function \(f(F, \omega(G))\) such that \(\chi(G)\leq f(F, \omega(G))\) for any \(F\)-free graph \(G\). Let \(C_{2, 1, n}\) be the tree with order \(n+4\) obtained from \(P_4\) and \(P_n\) by joining a vertex \(v\) (with \(d_{P_4} (v)=2\)) of \(P_4\) and one endvertex of \(P_n, C_{2, n, 2}\) be the tree with order \(n+5\) obtained from \(P_5\) and \(P_n\) by joining the middle vertex of \(P_5\) and one endvertex of \(P_n\). It is proved that every triangle-free, \(C_4\)-free and \(T\)-free graph is \((n+2)\)-colourable where \(T\cong C_{2, 1, n+1}\) or \(T\cong C_{2, n, 2}\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C05 Trees
Full Text: DOI