Every finite graph is a full subgraph of a rigid graph

DOI10.1016/0095-8956(71)90038-4zbMath0231.05107OpenAlexW1974819867WikidataQ115954248 ScholiaQ115954248MaRDI QIDQ2550402

Václav Chvátal, Jaroslav Nešetřil, Luděk Kučera, Pavol Hell

Publication date: 1971

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

Full work available at URL: https://doi.org/10.1016/0095-8956(71)90038-4

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

Chromatically optimal rigid graphs ⋮ Endomorphism monoids and topological subgraphs of graphs ⋮ On the order of countable graphs ⋮ Quotients of rigid graphs ⋮ Asymmetric trees with two prescribed degrees ⋮ On some strongly rigid families of graphs and the full embeddings they induce ⋮ Automorphism group and category of cospectral graphs ⋮ Full embeddings into some categories of graphs ⋮ A surprising permanence of old motivations (a not-so-rigid story) ⋮ Homomorphisms of unary algebras with a given quotient ⋮ Gruppenuniversalität und Homogenisierbarkeit

Cites Work

• Unnamed Item
• Unnamed Item
• On full embeddings of categories of algebras
• Symmetric relations (undirected graphs) with given semigroups
• On Rigid Undirected Graphs