Recent zbMATH articles in MSC 05C75https://zbmath.org/atom/cc/05C752021-06-15T18:09:00+00:00WerkzeugGraph classes with linear Ramsey numbers.https://zbmath.org/1460.051222021-06-15T18:09:00+00:00"Alecu, Bogdan"https://zbmath.org/authors/?q=ai:alecu.bogdan"Atminas, Aistis"https://zbmath.org/authors/?q=ai:atminas.aistis"Lozin, Vadim"https://zbmath.org/authors/?q=ai:lozin.vadim-v"Zamaraev, Viktor"https://zbmath.org/authors/?q=ai:zamaraev.victor-aSummary: The Ramsey number \(R_X ( p , q )\) for a class of graphs \(X\) is the minimum \(n\) such that every graph in \(X\) with at least \(n\) vertices has either a clique of size \(p\) or an independent set of size \(q\). We say that Ramsey numbers are linear in \(X\) if there is a constant \(k\) such that \(R_X ( p , q ) \leq k ( p + q )\) for all \(p\), \(q\). In the present paper we conjecture that if \(X\) is a hereditary class defined by finitely many forbidden induced subgraphs, then Ramsey numbers are linear in \(X\) if and only if \(X\) excludes a forest, a disjoint union of cliques and their complements. We prove the ``only if'' part of this conjecture and verify the ``if'' part for a variety of classes. We also apply the notion of linearity to bipartite Ramsey numbers and reveal a number of similarities and differences between the bipartite and non-bipartite case.Connectivity for kite-linked graphs.https://zbmath.org/1460.051012021-06-15T18:09:00+00:00"Liu, Runrun"https://zbmath.org/authors/?q=ai:liu.runrun"Rolek, Martin"https://zbmath.org/authors/?q=ai:rolek.martin"Stephens, D. Christopher"https://zbmath.org/authors/?q=ai:stephens.d-christopher"Ye, Dong"https://zbmath.org/authors/?q=ai:ye.dong.1|ye.dong.2"Yu, Gexin"https://zbmath.org/authors/?q=ai:yu.gexinNew examples of minimal non-strongly-perfect graphs.https://zbmath.org/1460.050712021-06-15T18:09:00+00:00"Chudnovsky, Maria"https://zbmath.org/authors/?q=ai:chudnovsky.maria"Dibek, Cemil"https://zbmath.org/authors/?q=ai:dibek.cemil"Seymour, Paul"https://zbmath.org/authors/?q=ai:seymour.paul-dSummary: A graph is strongly perfect if every induced subgraph \(H\) has a stable set that meets every nonempty maximal clique of \(H\). The characterization of strongly perfect graphs by a set of forbidden induced subgraphs is not known. Here we provide several new minimal non-strongly-perfect graphs.Integral equienergetic non-isospectral unitary Cayley graphs.https://zbmath.org/1460.050862021-06-15T18:09:00+00:00"Podestá, Ricardo A."https://zbmath.org/authors/?q=ai:podesta.ricardo-a"Videla, Denis E."https://zbmath.org/authors/?q=ai:videla.denis-eFor a finite abelian group \(G\) and a set \(S \subseteq G\) with \(S=-S\), the Cayley graph \(\mathrm{X}(G,S)\) is the graph whose vertices are the elements of \(G\), with an edge between \(g\) and \(h\) whenever \(h-g \in S\). Similarly, the Cayley sum graph \(\mathrm{X}^+(G,S)\) also has the elements of \(G\) as its vertices, with an edge between \(g\) and \(h\) whenever \(g+h \in S\).
The authors observe that \(\mathrm{X}(G,S)\) and \(\mathrm{X}^+(G,S)\) have equal energy but in general will not have the same spectra (although their spectra may sometimes coincidentally be the same).
In particular, if \(G\) is taken to be a ring \(R\) under addition, and \(S=R^\ast\) is the collection of units of \(R\), then the authors determine conditions under which \(\mathrm{X}(R,R^\ast)\) and \(\mathrm{X}^+(R,R^\ast)\) have the same energy, do not have the same spectra, have all integral eigenvalues, and are connected and non-bipartite graphs. In particular, if \(R\) is a local ring only the condition \(|R|\) odd is required; also, the authors characterise when either of these graphs is strongly regular. They also study when \(\mathrm{X}(G,S)\) has the same energy as its complement, and situations in which the complement does not have the same spectrum as the original graph.
Finally, the authors consider whether or not any of the graphs being studied is Ramanujan, and construct large sets of connected graphs that have the same energy, different spectra, and integral eigenvalues.
Reviewer: Joy Morris (Lethbridge)Rickart \(\ast\)-rings with planar zero-divisor graphs.https://zbmath.org/1460.160442021-06-15T18:09:00+00:00"Patil, Avinash"https://zbmath.org/authors/?q=ai:patil.avinash-aSummary: In this paper, we characterize all finite Rickart \(\ast\)-rings whose zero-divisor graphs are planar.The Zariski topology-graph of modules over commutative rings. II.https://zbmath.org/1460.130192021-06-15T18:09:00+00:00"Ansari-Toroghy, H."https://zbmath.org/authors/?q=ai:ansari-toroghy.habibollah"Habibi, S."https://zbmath.org/authors/?q=ai:habibi.shokoofe|habibi.shokoufehSummary: Let \(M\) be a module over a commutative ring \(R\). In this paper, we continue our study about the Zariski topology-graph \(G(\tau_T)\) which was introduced in [the authors, Commun. Algebra 42, No. 8, 3283--3296 (2014; Zbl 1295.13016)]. For a non-empty subset \(T\) of \(\text{Spec}(M)\), we obtain useful characterizations for those modules \(M\) for which \(G(\tau_T)\) is a bipartite graph. Also, we prove that if \(G(\tau_T)\) is a tree, then \(G(\tau_T)\) is a star graph. Moreover, we study coloring of Zariski topology-graphs and investigate the interplay between \(\chi (G(\tau_T))\) and \(\omega (G(\tau_T))\).Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs.https://zbmath.org/1460.051612021-06-15T18:09:00+00:00"Atminas, A."https://zbmath.org/authors/?q=ai:atminas.aistis"Brignall, R."https://zbmath.org/authors/?q=ai:brignall.robert"Lozin, V."https://zbmath.org/authors/?q=ai:lozin.vadim-v"Stacho, J."https://zbmath.org/authors/?q=ai:stacho.jurajSummary: We discover new hereditary classes of graphs that are minimal (with respect to set inclusion) of unbounded clique-width. The new examples include split permutation graphs and bichain graphs. Each of these classes is characterised by a finite list of minimal forbidden induced subgraphs. These, therefore, disprove a conjecture due to \textit{J. Daligault} et al. [Order 27, No. 3, 301--315 (2010; Zbl 1209.05210)] claiming that all such minimal classes must be defined by infinitely many forbidden induced subgraphs.
In the same paper, Daligault, Rao and Thomassé make another conjecture that every hereditary class of unbounded clique-width must contain a labelled infinite antichain. We show that the two example classes we consider here satisfy this conjecture. Indeed, they each contain a canonical labelled infinite antichain, which leads us to propose a stronger conjecture: that every hereditary class of graphs that is minimal of unbounded clique-width contains a canonical labelled infinite antichain.An extension of annihilating-ideal graph of commutative rings.https://zbmath.org/1460.130142021-06-15T18:09:00+00:00"Kerahroodi, Mahtab Koohi"https://zbmath.org/authors/?q=ai:kerahroodi.mahtab-koohi"Nabaei, Fatemeh"https://zbmath.org/authors/?q=ai:nabaei.fatemehSummary: Let \(R\) be a commutative ring with unity. The extension of annihilating-ideal graph of \(R\), \(\overline{\mathbb{AG}}(R)\), is the graph whose vertices are nonzero annihilating ideals of \(R\) and two distinct vertices \(I\) and \(J\) are adjacent if and only if there exist \(n,m\in\mathbb{N}\) such that \(I^nJ^m=(0)\) with \(I^n,J^m\neq (0)\). First, we differentiate when \(\mathbb{AG}(R)\) and \(\overline{\mathbb{AG}}(R)\) coincide. Then, we have characterized the diameter and the girth of \(\overline{\mathbb{AG}}(R)\) when \(R\) is a finite direct products of rings. Moreover, we show that \(\overline{\mathbb{AG}}(R)\) contains a cycle, if \(\overline{\mathbb{AG}}(R)\neq\mathbb{AG}(R)\).Partitioning cographs into two forests and one independent set.https://zbmath.org/1460.051552021-06-15T18:09:00+00:00"Hell, Pavol"https://zbmath.org/authors/?q=ai:hell.pavol"Hernández-Cruz, César"https://zbmath.org/authors/?q=ai:hernandez-cruz.cesar"Sanyal, Anurag"https://zbmath.org/authors/?q=ai:sanyal.anuragThe authors characterize when a cograph has a partition into \(p=2\) forests and \(q=1\) independent set by describing a family of nine minimal obstructions. Namely, a cograph can be partitioned into two forests and one independent set if and only if it does not contain an induced subgraph isomorphic to one of those nine obstructions.
In the cases \(p=0\), \(p=1\) and \(q=0\), there were already a list of cograph obstructions known. For \(p=0\), a cograph can be partitioned into \(q\) independent sets if and only if it does not contain \(K_{q+1}\). For \(p=1\), the list of minimal cograph obstructions contains the two graphs \(K_{q+3}\) and \(\overline{q+2K_2}\). In particular, both lists are uniform in the sense that they describe uniformly all forbidden subgraphs for any value of \(q\) and fixed \(p\in \{0,1\}\). The authors investigate whether such a uniform description can be found in the case \(p=2\). Their main result (a list of nine cograph obstructions for \(p=2, q=1\)) implies that this is not the case, as not all of those nine cographs are a generalization of the seven known cograph obstructions for \(p=2, q=0\) given in [\textit{S. G. Hermosillo de la Maza} et al., ``Vertex arboricity of cographs'', Preprint, \url{arXiv:1907.07286}].
The article concludes by sketching how the algorithm given in [loc. cit.] can be modified to certify the non-existence of a partition of a cograph into two forests and one independent set by returning one of the nine minimal obstructions.
For the entire collection see [Zbl 1435.68020].
Reviewer: Isabel Beckenbach (Berlin)