Title: Inductive $k$-independent graphs and $c$-colorable subgraphs in scheduling: A review,
Abstract: Inductive $k$-independent graphs generalize chordal graphs and have recently
been advocated in the context of interference-avoiding wireless communication
scheduling. The NP-hard problem of finding maximum-weight induced $c$-colorable
subgraphs, which is a generalization of finding maximum independent sets,
naturally occurs when selecting $c$ sets of pairwise non-conflicting jobs
(modeled as graph vertices). We investigate the parameterized complexity of
this problem on inductive $k$-independent graphs. We show that the Independent
Set problem is W[1]-hard even on 2-simplicial 3-minoes---a subclass of
inductive 2-independent graphs. In contrast, we prove that the more general
Maximum $c$-Colorable Subgraph problem is fixed-parameter tractable on
edge-wise unions of cluster and chordal graphs, which are 2-simplicial. In both
cases, the parameter is the solution size. Aside from this, we survey other
graph classes between inductive 1-inductive and inductive 2-inductive graphs
with applications in scheduling.