Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Narrowing the Complexity Gap for Colouring ($C_s$,$P_t$)-Free Graphs   For a positive integer $k$ and graph $G=(V,E)$, a $k$-colouring of $G$ is a
mapping $c: V\rightarrow\{1,2,\ldots,k\}$ such that $c(u)\neq c(v)$ whenever
$uv\in E$. The $k$-Colouring problem is to decide, for a given $G$, whether a
$k$-colouring of $G$ exists. The $k$-Precolouring Extension problem is to
decide, for a given $G=(V,E)$, whether a colouring of a subset of $V$ can be
extended to a $k$-colouring of $G$. A $k$-list assignment of a graph is an
allocation of a list -a subset of $\{1,\ldots,k\}$- to each vertex, and the
List $k$-Colouring problem is to decide, for a given $G$, whether $G$ has a
$k$-colouring in which each vertex is coloured with a colour from its list. We
continued the study of the computational complexity of these three decision
problems when restricted to graphs that contain neither a cycle on $s$ vertices
nor a path on $t$ vertices as induced subgraphs (for fixed positive integers
$s$ and~$t$).

26
The categories of this paper are: bayes-an
0
The categories of this paper are: hep-ph
13
The categories of this paper are: quant-ph
20
The categories of this paper are: acc-phys
37
The categories of this paper are: supr-con
14
The categories of this paper are: math-ph
12
The categories of this paper are: nucl-th
11
The categories of this paper are: hep-lat
30
The categories of this paper are: q-alg
9
The categories of this paper are: nlin
35
The categories of this paper are: mtrl-th
17
The categories of this paper are: q-fin
27
The categories of this paper are: comp-gas
19
The categories of this paper are: eess
10
The categories of this paper are: q-bio
5
The categories of this paper are: gr-qc