On realizations of point determining graphs, and obstructions to full homomorphisms

DOI10.1016/j.disc.2006.11.026zbMath1135.05042OpenAlexW2052851790MaRDI QIDQ2477389

Tomás Feder, Pavol Hell

Publication date: 13 March 2008

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

Full work available at URL: https://doi.org/10.1016/j.disc.2006.11.026

zbMATH Keywords

polynomial algorithmsforbidden subgraph characterizationsfull homomorphismspoint determining graphs

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Editing Graphs Into Few Cliques: Complexity, Approximation, and Kernelization Schemes, Matrix partitions of split graphs, Colourings, homomorphisms, and partitions of transitive digraphs, Obstructions to partitions of chordal graphs, Gaps in full homomorphism order, Full-homomorphisms to paths and cycles, Matrix partitions of perfect graphs, Colouring, constraint satisfaction, and complexity, Graph partitions with prescribed patterns, Join colourings of chordal graphs, Connected obstructions to full graph homomorphisms, Dualities in full homomorphisms, Point determining digraphs, \(\{ 0,1 \}\)-matrix partitions, and dualities in full homomorphisms, Matrix Partitions with Finitely Many Obstructions

Cites Work

• List matrix partitions of chordal graphs
• On the complexity of H-coloring
• The nucleus of a point determining graph
• The edge nucleus of a point-determining graph
• 1-factors of point determining graphs
• Line-critical point determining and point distinguishing graphs
• Matrix partitions of perfect graphs
• Point determination in graphs
• Complexity of graph partition problems
• Matrix Partitions with Finitely Many Obstructions
• List Partitions
• Unnamed Item
• Unnamed Item