Density via duality.

DOI10.1016/S0304-3975(01)00263-8zbMath1058.05062OpenAlexW1994512037MaRDI QIDQ1853500

Jaroslav Nešetřil, Claude Tardif

Publication date: 21 January 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00263-8

zbMATH Keywords

density theoremhomomorphism duality

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items

On the restricted homomorphism problem, Obstructions to locally injective oriented improper colourings

Cites Work

• Unnamed Item
• The chromatic number of the product of two 4-chromatic graphs is 4
• On the complexity of H-coloring
• Color-families are dense
• Colorings and orientations of graphs
• On classes of relations and graphs determined by subobjects and factorobjects
• A survey on Hedetniemi's conjecture
• Duality theorems for finite structures (characterising gaps and good characterisations)
• Lattices arising in categorial investigations of Hedetniemi's conjecture
• Acyclic orientations of graphs
• Graph Theory and Probability
• A Theorem on n-Coloring the Points of a Linear Graph
• The Homomorphism Structure of Classes of Graphs
• Duality and Polynomial Testing of Tree Homomorphisms
• Nombre chromatique et plus longs chemins d'un graphe
• Operations with structures