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

DOI10.1016/j.disc.2006.11.026zbMath1135.05042MaRDI 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 algorithms; forbidden subgraph characterizations; full homomorphisms; point determining graphs

Mathematics Subject Classification ID

05C75: Structural characterization of families of graphs

05C15: Coloring of graphs and hypergraphs

05C62: Graph representations (geometric and intersection representations, etc.)

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• 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