Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Decomposing graphs into interval colorable subgraphs and no-wait
  multi-stage schedules   A graph $G$ is called interval colorable if it has a proper edge coloring
with colors $1,2,3,\dots$ such that the colors of the edges incident to every
vertex of $G$ form an interval of integers. Not all graphs are interval
colorable; in fact, quite few families have been proved to admit interval
colorings. In this paper we introduce and investigate a new notion, the
interval coloring thickness of a graph $G$, denoted
${\theta_{\mathrm{int}}}(G)$, which is the minimum number of interval colorable
edge-disjoint subgraphs of $G$ whose union is $G$.
  Our investigation is motivated by scheduling problems with compactness
requirements, in particular, problems whose solution may consist of several
schedules, but where each schedule must not contain any waiting periods or idle
times for all involved parties. We first prove that every connected properly
$3$-edge colorable graph with maximum degree $3$ is interval colorable, and
using this result, we deduce an upper bound on ${\theta_{\mathrm{int}}}(G)$ for
general graphs $G$. We demonstrate that this upper bound can be improved in the
case when $G$ is bipartite, planar or complete multipartite and consider some
applications in timetabling.

12
The categories of this paper are: nucl-th
4
The categories of this paper are: cond-mat
13
The categories of this paper are: quant-ph
32
The categories of this paper are: atom-ph
22
The categories of this paper are: chao-dyn
33
The categories of this paper are: plasm-ph
18
The categories of this paper are: econ
34
The categories of this paper are: chem-ph
23
The categories of this paper are: solv-int
0
The categories of this paper are: hep-ph
14
The categories of this paper are: math-ph
15
The categories of this paper are: nucl-ex
3
The categories of this paper are: physics
30
The categories of this paper are: q-alg
20
The categories of this paper are: acc-phys
7
The categories of this paper are: hep-th