Recent zbMATH articles in MSC 05C76 https://www.zbmath.org/atom/cc/05C76 2021-04-16T16:22:00+00:00 Werkzeug $$\varDelta$$-convexity number and $$\varDelta$$-number of graphs and graph products. https://www.zbmath.org/1456.05132 2021-04-16T16:22:00+00:00 "Anand, Bijo S." https://www.zbmath.org/authors/?q=ai:anand.bijo-s "Narasimha-Shenoi, Prasanth G." https://www.zbmath.org/authors/?q=ai:prasanth.g-narasimha-shenoi "Ramla, Sabeer Sain" https://www.zbmath.org/authors/?q=ai:ramla.sabeer-sain Summary: The $$\varDelta$$-interval of $$u,v\in V(G), I_{\varDelta}(u,v)$$, is the set formed by $$u, v$$ and every $$w$$ in $$V(G)$$ such that $$\{u,v,w\}$$ is a triangle $$(K_3)$$ of $$G$$. A set $$S$$ of vertices such that $$I_{\varDelta}(S)=V(G)$$ is called a $$\varDelta$$-set. $$\varDelta$$-number is the minimum cardinality of a $$\varDelta$$-set. $$\varDelta$$-graph is a graph with all the vertices lie on some triangles. If a block graph is a $$\varDelta$$-graph, then we say that it is a block $$\varDelta$$-graph. A set $$S\subseteq V(G)$$ is $$\varDelta$$-convex if there is no vertex $$u\in V(G)\setminus S$$ forming a triangle with two vertices of $$S$$. The convexity number of a graph $$G$$ with respect to the $$\varDelta$$-convexity is the maximum cardinality of a proper convex subset of $$G$$. We have given an exact value for the convexity number of block $$\varDelta$$-graphs with diameter $${\le}3$$, block $$\varDelta$$-graphs with diameter $${>}3$$ and the two standard graph products (Strong, Lexicographic products), a bound for Cartesian product. Also discussed some bounds for $$\varDelta$$-number and a realization is done for the $$\varDelta$$-number and the hull number. For the entire collection see [Zbl 1435.68020]. Ramsey numbers for line graphs. https://www.zbmath.org/1456.05113 2021-04-16T16:22:00+00:00 "Abbasi, Huzaifa" https://www.zbmath.org/authors/?q=ai:abbasi.huzaifa "Basavaraju, Manu" https://www.zbmath.org/authors/?q=ai:basavaraju.manu "Gurushankar, Eeshwar" https://www.zbmath.org/authors/?q=ai:gurushankar.eeshwar "Jivani, Yash" https://www.zbmath.org/authors/?q=ai:jivani.yash "Srikanth, Deepak" https://www.zbmath.org/authors/?q=ai:srikanth.deepak Summary: Given a graph, the classical Ramsey number $$R(k,l)$$ is the least number of vertices that need to be in the graph for the existence of a clique of size $$k$$ or an independent set of size $$l$$. Finding $$R(k,l)$$ exactly has been a notoriously hard problem. Even $$R(k,3)$$ has not been determined for all values of $$k$$. Hence finding the Ramsey number for subclasses of graphs is an interesting question. It is known that even for claw-free graphs, finding Ramsey number is as hard as for general graphs for infinite number of cases. Line graphs are an important subclass of claw-free graphs. The question with respect to line graph $$L(G)$$ is equivalent to the minimum number of edges the underlying graph $$G$$ needs to have for the existence of a vertex with degree $$k$$ or a matching of size $$l$$. \textit{V. Chvátal} and \textit{D. Hanson} [J. Comb. Theory, Ser. B 20, 128--138 (1976; Zbl 0324.05119)] determined this exactly for line graphs of simple graphs. Later \textit{N. Balachandran} and \textit{N. Khare} [Discrete Math. 309, No. 12, 4176--4180 (2009; Zbl 1218.05120)] gave the same bounds with a different proof. In this paper we find Ramsey numbers for line graph of multi graphs thereby extending the results of Chvátal and Hanson [loc. cit.]. Here we determine the maximum number of edges that a multigraph can have, when its matching number, multiplicity, and maximum degree are bounded, and characterize such graphs. For the entire collection see [Zbl 1435.68020]. 2-distance chromatic number of some graph products. https://www.zbmath.org/1456.05062 2021-04-16T16:22:00+00:00 "Ghazi, Ghazale" https://www.zbmath.org/authors/?q=ai:ghazi.ghazale "Rahbarnia, Freydoon" https://www.zbmath.org/authors/?q=ai:rahbarnia.freydoon "Tavakoli, Mostafa" https://www.zbmath.org/authors/?q=ai:tavakoli.mostafa On spectra and real energy of complex weighted digraphs. https://www.zbmath.org/1456.05098 2021-04-16T16:22:00+00:00 "Bhat, Mushtaq A." https://www.zbmath.org/authors/?q=ai:bhat.mushtaq-a "Pirzada, S." https://www.zbmath.org/authors/?q=ai:pirzada.shariefuddin "Rada, J." https://www.zbmath.org/authors/?q=ai:rada.juan The authors studied spectral properties of complex weighted digraphs. Also, they showed that a complex weighted digraph $$D$$ is balanced if and only if $$D$$ and $$|D|$$ have the same spectrum, where $$|D|$$ is the absolute value weighted digraph of $$D$$, that is, the digraph obtained by replacing the weight of each arc by its absolute value. They extended the concept of real energy to complex weighted digraphs and obtained extremal energy unicyclic complex weighted digraphs with cycle weight in the punctured disk $$\{z\in C : |z|\leq 1\}\{0\}$$. The authors considered a family of complex weighted digraphs $$D_{n,h}$$, in which each digraph has order $$n$$ and cycles of length $$h\geq 2$$ only with constant complex weight $$c=a+ib$$. For each $$D\in D_{n,h}$$, the real energy of $$D$$ is related to the real energy of the unweighted cycle of length $$h$$ and in some special cases real energy can be compared using quasiorder relations on coefficients of the characteristic polynomial. Finally, they obtained upper bounds on the real energy which generalize those known for unweighted digraphs and signed digraphs. The article has many avenues and interesting results. It is useful to researchers working on graphs and matrices. Reviewer: V. Lokesha (Bangalore) On the circular altitude of graphs. https://www.zbmath.org/1456.05091 2021-04-16T16:22:00+00:00 "Shaebani, Saeed" https://www.zbmath.org/authors/?q=ai:shaebani.saeed Summary: Peter Cameron introduced the concept of the circular altitude of graphs, a parameter which was shown by Bamberg et al. that provides a lower bound on the circular chromatic number. In this paper, we investigate this parameter and show that the circular altitude of a graph is equal to the maximum of circular altitudes of its blocks. Also, we show that homomorphically equivalent graphs have the same circular altitudes. Finally, we prove that the circular altitude of the Cartesian product of two graphs is equal to the maximum of circular altitudes of its factors. Diameter of colorings under Kempe changes. https://www.zbmath.org/1456.05056 2021-04-16T16:22:00+00:00 "Bonamy, Marthe" https://www.zbmath.org/authors/?q=ai:bonamy.marthe "Heinrich, Marc" https://www.zbmath.org/authors/?q=ai:heinrich.marc "Ito, Takehiro" https://www.zbmath.org/authors/?q=ai:ito.takehiro "Kobayashi, Yusuke" https://www.zbmath.org/authors/?q=ai:kobayashi.yusuke "Mizuta, Haruka" https://www.zbmath.org/authors/?q=ai:mizuta.haruka "Mühlenthaler, Moritz" https://www.zbmath.org/authors/?q=ai:muhlenthaler.moritz "Suzuki, Akira" https://www.zbmath.org/authors/?q=ai:suzuki.akira "Wasa, Kunihiro" https://www.zbmath.org/authors/?q=ai:wasa.kunihiro Summary: Given a $$k$$-coloring of a graph $$G$$, a Kempe-change for two colors $$a$$ and $$b$$ produces another $$k$$-coloring of $$G$$, as follows: first choose a connected component in the subgraph of $$G$$ induced by the two color classes of $$a$$ and $$b$$, and then swap the colors $$a$$ and $$b$$ in the component. Two $$k$$-colorings are called Kempe-equivalent if one can be transformed into the other by a sequence of Kempe-changes. We consider two problems, defined as follows: First, given two $$k$$-colorings of a graph $$G$$, Kempe Reachability asks whether they are Kempe-equivalent; and second, given a graph $$G$$ and a positive integer $$k$$, Kempe Connectivity asks whether any two $$k$$-colorings of $$G$$ are Kempe-equivalent. We analyze the complexity of these problems from the viewpoint of graph classes. We prove that Kempe Reachability is $$\mathsf{PSPACE}$$-complete for any fixed $$k \geq 3$$, and that it remains $$\mathsf{PSPACE}$$-complete even when restricted to three colors and planar graphs of maximum degree six. Furthermore, we show that both problems admit polynomial-time algorithms on chordal graphs, bipartite graphs, and cographs. For each of these graph classes, we give a non-trivial upper bound on the number of Kempe-changes needed in order to certify that two $$k$$-colorings are Kempe-equivalent. Indicated coloring of complete expansion and lexicographic product of graphs. https://www.zbmath.org/1456.05061 2021-04-16T16:22:00+00:00 "Francis, P." https://www.zbmath.org/authors/?q=ai:francis.peter-m|francis.p-j-peter-j "Raj, S. Francis" https://www.zbmath.org/authors/?q=ai:raj.s-francis "Gokulnath, M." https://www.zbmath.org/authors/?q=ai:gokulnath.m Summary: Indicated coloring is a slight variant of the game coloring which was introduced by \textit{A. Grzesik} [Discrete Math. 312, No. 23, 3467--3472 (2012; Zbl 1252.05062)]. In this paper, we show that for any graphs $$G$$ and $$H, G[H]$$ is $$k$$-indicated colorable for all $$k\ge\text{col}(G)\text{col}(H)$$. Also, we show that for any graph $$G$$ and for some classes of graphs $$H$$ with $$\chi(H)=\chi_i(H)=\ell$$, $$G[H]$$ is $$k$$-indicated colorable if and only if $$G[K_\ell]$$ is $$k$$-indicated colorable. As a consequence of this result we show that if $$G\in\mathcal{G}=\Big\{$$Chordal graphs, Cographs, $$\{P_5,C_4\}$$-free graphs, Complete multipartite graphs$$\Big\}$$ and $$H\in \mathcal{F}=\Big\{$$Bipartite graphs, Chordal graphs, Cographs, $$\{P_5,K_3\}$$-free graphs, $$\{P_5, \mathrm{paw}\}$$-free graphs, Complement of bipartite graphs, $$\{P_5,K_4,\mathrm{kite}, \mathrm{bull}\}$$-free graphs, connected $$\{P_6,C_5,\overline{P_5},K_{1,3}\}$$-free graphs which contain an induced $$C_6,\mathbb{K}[C_5](m_1, m_2 ,\dots,m_5),\{P_5,C_4\}$$-free graphs, connected $$\{P_5,\overline{P_2\cup P_3},\overline{P_5},\mathrm{dart}\}$$-free graphs which contain an induced $$C_5\Big\}$$, then $$G[H]$$ is $$k$$-indicated colorable for every $$k\ge\chi(G[H])$$. This serves as a partial answer to one of the questions raised by Grzesik in [loc. cit.]. For the entire collection see [Zbl 1435.68020]. Two faces of greedy leaf removal procedure on graphs. https://www.zbmath.org/1456.05033 2021-04-16T16:22:00+00:00 "Zhao, Jin-Hua" https://www.zbmath.org/authors/?q=ai:zhao.jinhua "Zhou, Hai-Jun" https://www.zbmath.org/authors/?q=ai:zhou.haijun Extending perfect matchings to Hamiltonian cycles in line graphs. https://www.zbmath.org/1456.05093 2021-04-16T16:22:00+00:00 "Abreu, Marién" https://www.zbmath.org/authors/?q=ai:abreu.marien "Gauci, John Baptist" https://www.zbmath.org/authors/?q=ai:gauci.john-baptist "Labbate, Domenico" https://www.zbmath.org/authors/?q=ai:labbate.domenico "Mazzuoccolo, Giuseppe" https://www.zbmath.org/authors/?q=ai:mazzuoccolo.giuseppe "Zerafa, Jean Paul" https://www.zbmath.org/authors/?q=ai:zerafa.jean-paul Summary: A graph admitting a perfect matching has the Perfect-Matching-Hamiltonian property (for short the PMH-property) if each of its perfect matchings can be extended to a Hamiltonian cycle. In this paper we establish some sufficient conditions for a graph $$G$$ in order to guarantee that its line graph $$L(G)$$ has the PMH-property. In particular, we prove that this happens when $$G$$ is (i) a Hamiltonian graph with maximum degree at most $$3$$, (ii) a complete graph, or (iii) an arbitrarily traceable graph. Further related questions and open problems are proposed along the paper. On Cartesian products of signed graphs. https://www.zbmath.org/1456.05133 2021-04-16T16:22:00+00:00 "Lajou, Dimitri" https://www.zbmath.org/authors/?q=ai:lajou.dimitri Summary: In this paper, we study the Cartesian product of signed graphs as defined by \textit{K. A. Germina} et al. [Linear Algebra Appl. 435, No. 10, 2432--2450 (2011; Zbl 1222.05223)]. Here we focus on its algebraic properties and look at the chromatic number of some products. One of our main result is the unicity of the prime factor decomposition of signed graphs. This leads us to present an algorithm to compute this decomposition in quasi-linear time. Both these results use their counterparts for ordinary graphs as building blocks. We also study the signed chromatic number of graphs with underlying graph of the form $$P_n \square P_m$$, of products of signed paths, of products of signed complete graphs and of products of signed cycles, that is the minimum order of a signed graph to which they admit a homomorphism. For the entire collection see [Zbl 1435.68020].