Interval vertex-coloring of a graph with forbidden colors

DOI10.1016/0012-365X(89)90204-5MaRDI QIDQ1823960zbMATH OpenFDO

Authors Marek Kubale

Publication date 1989

Published in Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

chromatic numberNP-completenesspolynomial-time algorithminterval coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Recommendations

• 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

Cites work

• 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?)
• Computing and Combinatorics
• 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 NP-completeness column: An ongoing guide
• The complexity of scheduling independent two-processor tasks on dedicated processors

Cited in

(13)

• Precoloring extension. I: Interval graphs
• Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms
• Comparison of neural and heuristic methods for a timetabling problem
• About equivalent interval colorings of weighted graphs
• Interval edge coloring of a graph with forbidden colors
• INTERVAL VERTEX-COLORINGS OF CACTUS GRAPHS WITH RESTRICTIONS ON VERTICES
• Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems
• Preassignment requirements in chromatic scheduling
• Some results concerning the complexity of restricted colorings of graphs
• Restraints permitting the largest number of colourings
• Tree-coloring problems of bounded treewidth graphs
• A broken cycle theorem for the restrained chromatic function
• scientific article; zbMATH DE number 2230222 (Why is no real title available?)

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)