On the order of countable graphs

DOI10.1016/S0195-6698(03)00064-7MaRDI QIDQ1404996zbMATH OpenFDO

Authors J. Nešetřil, S. Shelah

Publication date 25 August 2003

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0404319

zbMATH Keywords

DensityPartially ordered setsRigid graphsUniversal graphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Models with special properties (saturated, rigid, etc.) (03C50) Coloring of graphs and hypergraphs (05C15) Combinatorics of partially ordered sets (06A07) Model theory of ordered structures; o-minimality (03C64) Applications of model theory (03C98)

Abstract: A set of graphs is said to be independent if there is no homomorphism between distinct graphs from the set. We consider the existence problems related to the independent sets of countable graphs. While the maximal size of an independent set of countable graphs is 2^omega the On Line problem of extending an independent set to a larger independent set is much harder. We prove here that singletons can be extended (``partnership theorem). While this is the best possible in general, we give structural conditions which guarantee independent extensions of larger independent sets. This is related to universal graphs, rigid graphs and to the density problem for countable graphs.

Recommendations

• scientific article; zbMATH DE number 887777
• On the number of independent sets in graphs with fixed independence number
• scientific article; zbMATH DE number 3068973
• Arithmetically maximal independent sets in infinite graphs
• Independence and chromatic densities of graphs

Cites work

• scientific article; zbMATH DE number 3650785 (Why is no real title available?)
• scientific article; zbMATH DE number 1341918 (Why is no real title available?)
• scientific article; zbMATH DE number 702561 (Why is no real title available?)
• scientific article; zbMATH DE number 3240401 (Why is no real title available?)
• A family of countable homogeneous graphs
• A rigid graph for every set
• Aspects of structural combinatorics. (Graph homomorphisms and their use)
• Chromatically optimal rigid graphs
• Color-families are dense
• Duality theorems for finite structures (characterising gaps and good characterisations)
• Every finite graph is a full subgraph of a rigid graph
• High Chromatic Rigid Graphs II
• Some universal graphs
• The Homomorphism Structure of Classes of Graphs
• Universal Infinite Partially Ordered Sets
• Universal graphs and universal functions
• Universal graphs with forbidden subgraphs and algebraic closure
• Universal graphs without large bipartite subgraphs
• Universal relational systems

Cited in

(16)

• Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
• The countable character of uncountable graphs
• A surprising permanence of old motivations (a not-so-rigid story)
• Increasing paths in countable graphs
• Linear colouring of binomial random graphs
• On the tree-depth of random graphs
• scientific article; zbMATH DE number 850765 (Why is no real title available?)
• On low tree-depth decompositions
• On treewidth and related parameters of random geometric graphs
• There is no universal countable random-free graph
• On low rank-width colorings
• Countable \(\alpha\)-extendable graphs
• On nowhere dense graphs
• Tree-depth, subgraph coloring and homomorphism bounds
• Strongly \(n\)-e.c. graphs and independent distinguishing labellings
• Counting homomorphisms to sparse graphs

This page was built for publication: On the order of countable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1404996)