Interval vertex-coloring of a graph with forbidden colors

DOI10.1016/0012-365X(89)90204-5zbMath0682.05033MaRDI QIDQ1823960

Marek Kubale

Publication date: 1989

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

NP-completenesspolynomial-time algorithmchromatic numberinterval coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items

INTERVAL VERTEX-COLORINGS OF CACTUS GRAPHS WITH RESTRICTIONS ON VERTICES ⋮ Preassignment requirements in chromatic scheduling ⋮ Some results concerning the complexity of restricted colorings of graphs ⋮ Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems ⋮ About equivalent interval colorings of weighted graphs ⋮ A broken cycle theorem for the restrained chromatic function ⋮ Restraints permitting the largest number of colourings ⋮ Tree-coloring problems of bounded treewidth graphs ⋮ Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms ⋮ Comparison of neural and heuristic methods for a timetabling problem ⋮ Unnamed Item ⋮ Interval edge coloring of a graph with forbidden colors

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of scheduling independent two-processor tasks on dedicated processors
• Scheduling unit-time tasks with integer release times and deadlines
• On Scheduling Unit-Length Jobs with Multiple Release Time/Deadline Intervals
• On the Complexity of Timetable and Multicommodity Flow Problems
• Computing and Combinatorics
• The NP-completeness column: An ongoing guide