The independence number of HH-homogeneous graphs and a classification of MB-homogeneous graphs

DOI10.1016/J.EJC.2019.103063MaRDI QIDQ2297920zbMATH OpenOpenAlexWikidataFDO

Authors Andrés Aranda, David Hartman

Publication date 20 February 2020

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

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

zbMATH Keywords

countably infinite connected HH-homogeneous graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: We show that the independence number of a countably infinite HH-homogeneous graph that does not contain the Rado graph as a spanning subgraph is finite and present a classification of MB-homogeneous graphs up to bimorphism-equivalence as a consequence.

Recommendations

• scientific article; zbMATH DE number 1557817
• Independence and graph homomorphisms graph homomorphisms
• On the \(k\)-independence number of graphs
• On the k-independence number in graphs
• The indivisibility of the homogeneous \(K_ n\)-free graphs
• The relation between the \(H\)-rank of a mixed graph and the independence number of its underlying graph
• Independent sets of m,n-gonal graphs
• On graphs whose domination numbers equal their independent domination numbers
• scientific article; zbMATH DE number 4041970
• Independence saturation number of some classes of graphs

Cites work

• A note on Fiedler value of classes with sublinear separators
• Countable Ultrahomogeneous Undirected Graphs
• Homomorphism-homogeneous \(L\)-colored graphs
• Homomorphism-homogeneous graphs
• Homomorphism-Homogeneous Relational Structures
• Permutation monoids and MB-homogeneity for graphs and relational structures
• Some more notions of homomorphism-homogeneity
• The classification of countable homogeneous directed graphs and countable homogeneous 𝑛-tournaments
• Towards a Ryll-Nardzewski-type theorem for weakly oligomorphic structures
• Two Fraïssé-style theorems for homomorphism-homogeneous relational structures

Cited in

(6)

• On a problem of Cameron's on inexhaustible graphs
• IB-homogeneous graphs
• The poset of morphism-extension classes of countable graphs
• The classification of homomorphism homogeneous tournaments
• Towards the classification of polymorphism-homogeneous metric spaces
• MB-homogeneous graphs and some new HH-homogeneous graphs

This page was built for publication: The independence number of HH-homogeneous graphs and a classification of MB-homogeneous graphs

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