Interval vertex-coloring of a graph with forbidden colors
The classical model of coloring the vertices of a graph with single colors so that no two adjacent vertices are colored the same is too limited to be useful in many practical applications. Therefore one must consider more general notions of graph coloring and this article is devoted to one of such generalizations. The author considers a problem of interval coloring the vertices of a graph under the stipulation that certain colors cannot be used for some vertices. Lower and upper bounds on the minimum number of colors required for such a coloring are given. Since the general problem is NP-complete, he investigates its complexity in some special cases with a particular reference to those that can be solved by a polynomial-time algorithm.
- Interval edge coloring of a graph with forbidden colors
- INTERVAL VERTEX-COLORINGS OF CACTUS GRAPHS WITH RESTRICTIONS ON VERTICES
- Interval non-total colorable graphs
- Vertex colourings of multigraphs with forbiddances on edges
- Intervalizing \(k\)-colored graphs
- Interval edge-colorings of complete graphs
- Forbidden subgraphs of coloring graphs
- Coloring graphs with forbidden induced subgraphs
- scientific article; zbMATH DE number 17824
- Coloring graphs characterized by a forbidden subgraph
- Computing and Combinatorics
- scientific article; zbMATH DE number 3841898 (Why is no real title available?)
- scientific article; zbMATH DE number 3735847 (Why is no real title available?)
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- On Scheduling Unit-Length Jobs with Multiple Release Time/Deadline Intervals
- On the Complexity of Timetable and Multicommodity Flow Problems
- Scheduling unit-time tasks with integer release times and deadlines
- The complexity of scheduling independent two-processor tasks on dedicated processors
- The NP-completeness column: An ongoing guide
- Some results concerning the complexity of restricted colorings of graphs
- Precoloring extension. I: Interval graphs
- Comparison of neural and heuristic methods for a timetabling problem
- Interval edge coloring of a graph with forbidden colors
- Preassignment requirements in chromatic scheduling
- Restraints permitting the largest number of colourings
- Tree-coloring problems of bounded treewidth graphs
- Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems
- Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms
- scientific article; zbMATH DE number 2230222 (Why is no real title available?)
- A broken cycle theorem for the restrained chromatic function
- INTERVAL VERTEX-COLORINGS OF CACTUS GRAPHS WITH RESTRICTIONS ON VERTICES
- A polyhedral study of a relaxation of the routing and spectrum allocation problem
- Concurrency constrained scheduling with tree-like constraints
- About equivalent interval colorings of weighted graphs
This page was built for publication: Interval vertex-coloring of a graph with forbidden colors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1823960)
