In this paper, we introduce a new kind of generalized Fibonacci polynomials in the distance sense. We give a direct formula, a generating function and matrix generators for these polynomials. Moreover, we present a graph interpretation of these polynomials, their connections with Pascal’s triangle and we prove some identities for them.

We give a total graph interpretation of the numbers of the Fibonacci type. This graph interpretation relates to an edge colouring by monochromatic paths in graphs. We will show that it works for almost all numbers of the Fibonacci type. Moreover, we give the lower bound and the upper bound for the number of all(A1,2A1)-edge colourings in trees.

In this paper we use a graph interpretation of distance Fibonacci polynomials to get a new generalization of Lucas polynomials in the distance sense. We give a direct formula, a generating function and we prove some identities for generalized Lucas polynomials. We present Pascal-like triangles with left-justified rows filled with coefficients of these polynomials, in which one can observe some symmetric patterns. Using a general Q-matrix and a symmetric matrix of initial conditions we also define matrix generators for generalized Lucas polynomials.