Absolute retracts of split graphs
type: Item
instance of: scholarly article
title: Absolute retracts of split graphs
zbMATH Open document ID: 0812.05051
DOI: 10.1016/0012-365X(93)E0062-9
author: Sandi Klavžar
published in: Discrete Mathematics
publication date: 1995-05-09T00:00:00Z
review text: Let \(G= G(V,E)\) be a finite, undirected, connected and simple graph. \(G\) is called split if there is a partition \(V= K+ S\) of its vertex set into a complete set \(K\) and a stable set \(S\). This means that split graphs are ``half-way'' between bipartite graphs and their complements. Especially, \(G\) is a complete split graph if every vertex in \(S\) is adjacent to every vertex in \(K\). A subgraph \(H\subseteq G\) is a retract of \(G\) if there is an edge-preserving map \(r: V(G)\to V(H)\) with \(r(x)= x\) for all \(x\in V(H)\). A member \(G\) of a class \(\mathfrak C\) of graphs is called an absolute retract of the graphs in \(\mathfrak C\) if \(G\) is a retract of any \(M\in {\mathfrak C}\) containing \(G\) as an isometric and isochromatic subgraph. The author establishes structural properties depending on the maximum cardinalities \(\omega\) and \(\alpha\) of the subsets \(K\) and \(S\) of \(V(G)\), respectively, which characterize split graphs (Theorem 2.1). The main result of the paper is the statement that a split graph is an absolute retract of split graphs iff a partition of its vertex set into a stable set and a complete set is unique or it is a complete split graph (Theorem 3.2). Moreover the author proves equivalent conditions for split graphs with given \(\omega\) to be an absolute retract of the class \(\mathfrak C\) of all graphs (Theorem 3.6). And from this, for example, the results follow that every bipartite split graph is an absolute retract or that an \(n\)- chromatic split graph is an absolute retract iff there exists an unique \(n\)-colouring of \(G\). In the last section reflexive split graphs \(G\) are investigated (in this case a loop is added at each vertex of \(G\)). In Theorem 4.1 equivalent conditions for reflexive split graphs are given to be also an absolute retract. From this it follows that the split graphs \(J_ n\), \(n\geq 3\), are precisely the forbidden retracts of the absolute retracts of reflexive split graphs. Here \(J_…
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 701683
zbMATH Keywords: colouring
zbMATH Keywords: complete set
zbMATH Keywords: stable set
zbMATH Keywords: split graphs
zbMATH Keywords: complete split graph
zbMATH Keywords: retract
zbMATH Keywords: absolute retract
zbMATH Keywords: partition
zbMATH Keywords: reflexive split graphs
zbMATH Keywords: forbidden retracts
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
cites work: Absolute retracts of bipartite graphs
cites work: Dismantling absolute retracts of reflexive graphs
cites work: Clique graphs and Helly graphs
cites work: Q3772261
cites work: Q4193514
cites work: Q3328583
cites work: Q4049082
cites work: Absolute planar retracts and the four colour conjecture
cites work: Absolute Retracts and Varieties of Reflexive Graphs
cites work: A Classification of Reflexive Graphs: The use of “Holes”
cites work: The smallest graph variety containing all paths
cites work: Vertex-to-vertex pursuit in a graph
cites work: Minimal extensions of graphs to absolute retracts
cites work: Products of absolute retracts
cites work: A characterization of absolute retracts of n-chromatic graphs
full work available at URL: 0012-365x(93)e0062-9
OpenAlex ID: W2113859425
description: scientific article; zbMATH DE number 701683