We show that given an n-vertex graph G of diameter 3 we can decide if G is 3-colourable in time 2^{O(n^{2/3-ε})} for any ε < 1/33. This improves on the previous best algorithm of 2^{O((nlog n)^{2/3})} from Dębski, Piecyk and Rzążewski [Faster 3-coloring of small-diameter graphs, ESA 2021].

Abstract. Given [Formula: see text] graphs [Formula: see text], their intersection is the graph [Formula: see text]. Given [Formula: see text] graph classes [Formula: see text], we call the class [Formula: see text] the graph-intersection of [Formula: see text]. The main motivation for the work presented in this paper is to try to understand under which conditions graph-intersection preserves [Formula: see text]-boundedness. We consider the following two questions: (1) Which graph classes have the property that their graph-intersection with every [Formula: see text] -bounded class of graphs is [Formula: see text] -bounded? We call such a class intersectionwise [Formula: see text] -guarding. We prove that classes of graphs which admit a certain kind of decomposition are intersectionwise [Formula: see text]-guarding. We provide necessary conditions that a finite set of graphs [Formula: see text] should satisfy if the class of [Formula: see text]-free graphs is intersectionwise [Formula: see text]-guarding, and we characterize the intersectionwise [Formula: see text]-guarding classes which are defined by a single forbidden induced subgraph. (2) Which graph classes have the property that, for every positive integer [Formula: see text] , their [Formula: see text] -fold graph-intersection is [Formula: see text] -bounded? We call such a class intersectionwise self-[Formula: see text] -guarding. We study intersectionwise self-[Formula: see text]-guarding classes which are defined by a single forbidden induced subgraph, and we prove a result which allows us to construct intersectionwise self-[Formula: see text]-guarding classes from known intersectionwise [Formula: see text]-guarding classes.