Premium
On the existence of countable universal graphs
Author(s) -
Füredi Zoltán,
Komjáth Péter
Publication year - 1997
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199705)25:1<53::aid-jgt3>3.0.co;2-h
Subject(s) - mathematics , countable set , combinatorics , vertex (graph theory) , discrete mathematics , induced subgraph , class (philosophy) , graph , cograph , pathwidth , line graph , computer science , artificial intelligence
Let Forb(G) denote the class of graphs with countable vertex sets which do not contain G as a subgraph. If G is finite, 2‐connected, but not complete, then Forb(G) has no element which contains every other element of Forb(G) as a subgraph, i.e., this class contains no universal graph. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 53–58, 1997