On sparse graphs with given colorings and homomorphisms.

DOI10.1016/j.jctb.2003.06.001zbMath1033.05044OpenAlexW2169872958MaRDI QIDQ1425116

Xuding Zhu, Jaroslav Nešetřil

Publication date: 15 March 2004

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2003.06.001

zbMATH Keywords

characterizationMüller's theoremsparse incomparability lemma

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items

In praise of homomorphisms, Generalized signed graphs of large girth and large chromatic number, Uniquely \(D\)-colourable digraphs with large girth. II: Simplification via generalization, Dualities and dual pairs in Heyting algebras, Girth and λ $\lambda $‐choosability of graphs, Forbidden lifts (NP and CSP for combinatorialists), On tension-continuous mappings, Many Facets of Dualities, Colouring, constraint satisfaction, and complexity, Unnamed Item, A combinatorial constraint satisfaction problem dichotomy classification conjecture, A surprising permanence of old motivations (a not-so-rigid story), \(H\)-coloring dichotomy revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Chromatically optimal rigid graphs
• On colorings of graphs without short cycles
• Graph Theory and Probability
• Applications of product colouring
• Uniquely Colourable Graphs with Large Girth
• Circular colouring and graph homomorphism
• 25 pretty graph colouring problems
• Hedetniemi's conjecture and the retracts of a product of graphs
• Construction of sparse graphs with prescribed circular colorings