The complexity of nonrepetitive coloring

DOI10.1016/j.dam.2008.04.015zbMath1188.05066OpenAlexW1976058117MaRDI QIDQ1003751

Marcus Schaefer, Dániel Marx

Publication date: 4 March 2009

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

Full work available at URL: https://doi.org/10.1016/j.dam.2008.04.015

zbMATH Keywords

complexitypolynomial hierarchythue chromatic numbernonrepetitive coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

Acyclic edge-coloring using entropy compression ⋮ Characterisations and examples of graph classes with bounded expansion ⋮ Restricted coloring problems on graphs with few \(P_4\)'s ⋮ Nonrepetitive colouring via entropy compression

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pattern avoidance: themes and variations
• Thue type problems for graphs, points, and numbers
• Notes on nonrepetitive graph colouring
• Parametrized complexity theory.
• Estimation of sparse hessian matrices and graph coloring problems
• Star chromatic number
• Color-coding
• Nonrepetitive colorings of graphs

This page was built for publication: The complexity of nonrepetitive coloring