Some results concerning the complexity of restricted colorings of graphs
From MaRDI portal
Publication:1186161
DOI10.1016/0166-218X(92)90202-LzbMath0755.05036MaRDI QIDQ1186161
Publication date: 28 June 1992
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Related Items
Restricted coloring models for timetabling ⋮ Preassignment requirements in chromatic scheduling ⋮ Open shop problem with zero-one time operations and integer release date/deadline intervals ⋮ Restrictions and preassignments in preemptive open shop scheduling ⋮ List homomorphisms to reflexive graphs ⋮ Improved approximation algorithms for the max edge-coloring problem ⋮ Consensus models: computational complexity aspects in modern approaches to the list coloring problem ⋮ Solving Graph Partitioning Problems with Parallel Metaheuristics ⋮ Exploring the complexity boundary between coloring and list-coloring ⋮ Exploring the complexity boundary between coloring and list-coloring ⋮ Closing complexity gaps for coloring problems on \(H\)-free graphs ⋮ Approximating the max-edge-coloring problem ⋮ On the Maximum Edge Coloring Problem ⋮ A graph colouring model for assigning a heterogeneous workforce to a given schedule ⋮ On list \(k\)-coloring convex bipartite graphs ⋮ Extensions of coloring models for scheduling purposes ⋮ Interval edge coloring of a graph with forbidden colors ⋮ Edge dominating set and colorings on graphs with fixed clique-width
Cites Work
- Interval vertex-coloring of a graph with forbidden colors
- Scheduling unit-time tasks with integer release times and deadlines
- On Scheduling Unit-Length Jobs with Multiple Release Time/Deadline Intervals
- Algorithms for two bottleneck optimization problems
- The NP-Completeness of Edge-Coloring
- On Edge Coloring Bipartite Graphs
- On the Complexity of Timetable and Multicommodity Flow Problems
- A Combinatorial Theorem with an Application to Latin Rectangles
- Unnamed Item
- Unnamed Item
- Unnamed Item
