The complexity of generalized graph colorings

DOI10.1016/0166-218X(96)00096-0zbMath0879.05029MaRDI QIDQ1923585

Jason I. Brown

Publication date: 9 October 1996

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

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

complexityNP-completenesshypergraphsgeneralized graph colorings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items

Harary polynomials ⋮ Inductive graph invariants and approximation algorithms ⋮ Computational aspects of greedy partitioning of graphs ⋮ Algorithms for a shared resource scheduling problem in which some level of conflict is tolerable ⋮ On Computational Aspects of Greedy Partitioning of Graphs ⋮ Generalized Coloring of Permutations ⋮ On the complexity of generalized chromatic polynomials ⋮ Channel assignment problem and relaxed 2-distant coloring of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On generalized perfect graphs: Bounded degree and bounded edge perfection
• Graph minors. XX: Wagner's conjecture
• On the algorithmic complexity of coloring simple hypergraphs and Steiner triple systems
• Some undecidable problems involving the edge-coloring and vertex-coloring of graphs
• Coloring of universal graphs
• On the complexity of H-coloring
• Graph properties and hypergraph colourings
• The Ramsey property for graphs with forbidden complete subgraphs
• A Ramsey type problem concerning vertex colourings
• Chromatic partitions of a graph
• On cocolourings and cochromatic numbers of graphs
• Extremal results on defective colorings of graphs
• Generalizations of independence and chromatic numbers of a graph
• The subchromatic number of a graph
• Colour-critical graphs and hypergraphs
• On generalized graph colorings
• ON UNIQUELY -G k-COLOURABLE GRAPHS
• Two-Processor Scheduling with Start-Times and Deadlines
• A Construction of Uniquely C₄-free colourable Graphs
• On chromatic number of graphs and set-systems
• On chromatic number of finite set-systems
• On Partitioning Planar Graphs
• Graphs with Monochromatic Complete Subgraphs in Every Edge Coloring
• Colour Classes for r-Graphs
• Colouring Steiner quadruple systems

This page was built for publication: The complexity of generalized graph colorings