Article
Mathematics
Kinkar Chandra Das, Yilun Shang
Summary: This paper investigates the lower and upper bounds on the Sombor index of graph G in terms of graph parameters (clique number, chromatic number, number of pendant vertices, etc.) and characterizes the extremal graphs.
Article
Mathematics
Lkhagva Buyantogtokh, Batmend Horoldagva, Kinkar Chandra Das
Summary: Graph-based molecular structure descriptors, known as topological indices, are important for modeling the properties of molecules and designing compounds. In this paper, the graph invariant GRM(alpha) is studied, and extremal graphs with respect to GRM(alpha) are characterized.
Article
Mathematics, Applied
Shenwei Huang, Yiao Ju, T. Karthick
Summary: This paper studies the coloring of (P5, kite)-free graphs with small clique number. It provides color number bounds for different constraints on cliques and proves them for specific conditions. The paper also gives examples to demonstrate the tightness of the bounds and makes a conjecture for the more general case.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Yian Xu
Summary: The aim of this paper is to prove that a connected graph satisfying certain conditions is colorable.
APPLIED MATHEMATICS AND COMPUTATION
(2024)
Article
Mathematics
Luis D. Arreola-Bautista, Gerardo Reyna, Jesus Romero-Valencia, Jose M. Sigarreta
Summary: In this paper, we establish sufficient and necessary conditions for the existence of abelian subgroups of maximal order in a finite group G, using its commuting graph. The order of these subgroups is bounded by the sum of the cardinalities of the conjugacy classes and the centralizer of certain elements in G.
Article
Mathematics
Arnab Char, Thiyagarajan Karthick
Summary: This paper studies the class of (P-2 + P-3, P-2 + P-3)(SIC)-free graphs and proves that for every graph G with omega(G) >= 3, chi(G) = max {omega(G) + 3,[ 3/2 omega(G) - 1}, and the bound is tight.
JOURNAL OF GRAPH THEORY
(2023)
Article
Mathematics
Rui Li, Jinfeng Li, Di Wu
Summary: In this paper, we prove several results regarding the chromatic number of a graph and its relation to the freedom of specific graph structures, providing some restrictions for the chromatic number problem.
Review
Computer Science, Information Systems
Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, Paul G. Spirakis
Summary: This paper investigates the maximum clique problem for graphs with small intersection number and random intersection graphs, presenting a simple algorithm to find a maximum clique in polynomial time, especially when the number of labels is not too large. The study also proves that inferring the complete information of label choices for each vertex from the resulting random intersection graph is solvable with a unique solution using the maximum likelihood estimation method. The research contributes to the field by introducing the Single Label Clique Theorem to address the problem of forming large cliques from more than one label.
COMPUTER SCIENCE REVIEW
(2021)
Article
Mathematics
Arnab Char, T. Karthick
Summary: This study discovers that for graphs G that do not contain specified structures, if G contains K4, then the chromatic number chi(G) does not exceed 8; if G does not contain K4 but contains a variant of K4 called flag, then chi(G) does not exceed 9. Examples with tight bounds are also provided. Furthermore, for graphs G that do not contain the specified structure flag, with the condition w(G) >= 4, it is shown that chi(G) does not exceed max{8, 2w(G) - 3}, and the bound is tight when w(G) is 4, 5, or 6. Compared to previous literature, this study proposes better bounds.
DISCRETE MATHEMATICS
(2023)
Article
Mathematics
Hamid Reza Daneshpajouh
Summary: A family of sets is called star-shaped if all the members of the family have a point in common. The main aim of this paper is to provide a negative answer to the question raised by Aisenberg et al. regarding the existence of (n-2k+2) $(n-2k+2)$-colorings of the (n,k) $(n,k)$-Kneser graphs with more than k-1 $k-1$ many non-star-shaped color classes.
JOURNAL OF GRAPH THEORY
(2023)
Article
Mathematics, Applied
Dan Li, Rui Qin
Summary: This paper extends the study on maximizing the spectral radius under a fixed number of edges, concerning the A(alpha)-matrix.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2021)
Article
Mathematics
Kemal Toker
Summary: The paper explores the zero divisors and their properties of the partial transformation semigroup P-n, and defines an undirected graph Gamma(P-n) associated with P-n. It investigates the connectivity, diameter, girth, domination number, and degrees of the vertices of Gamma(P-n), and provides lower bounds for the clique number and chromatic number of Gamma(P-n).
TURKISH JOURNAL OF MATHEMATICS
(2021)
Article
Computer Science, Artificial Intelligence
R. Nikandish, M. Mehrara, M. J. Nikmehr
Summary: This paper investigates the properties of the essential annihilating-ideal graph of a ring, demonstrates that under certain conditions this graph is weakly perfect, and provides an explicit formula to calculate its clique number. Furthermore, it fully determines the structures of rings whose essential annihilating-ideal graphs have chromatic number 2, and examines properties such as twin-free clique number and edge chromatic number.
Article
Mathematics, Applied
Wei Wang, Zhidan Yan, Jianguo Qian
Summary: This paper proves that for any nonempty signed graph Σ with n vertices, the chromatic number is greater or equal to a function involving two eigenvalues and a parameter.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2021)
Article
Mathematics
Zemiao Dai, Muhammad Naeem, Zainab Shafaqat, Manzoor Ahmad Zahid, Shahid Qaisar
Summary: The advancement in coloring schemes of graphs is expanding over time to solve emerging problems. Recently, a new form of coloring, namely P-3-coloring, was introduced. The aim of this article is to determine the P-3-chromatic number of different well-known classes of bipartite graphs and present algorithms to produce a P-3-coloring of these classes with a minimum number of colors required.
Article
Mathematics
Weijun Fang, Jiejing Wen, Fang-Wei Fu
Summary: This paper proposes a sufficient condition to ensure that a Hermitian self-orthogonal GRS code is still a Hermitian self-orthogonal code. Based on this, a new general construction of infinitely families of quantum MDS codes is presented, and two new constructions of quantum MDS codes with flexible parameters are given using the trace function and norm function over finite fields. The constructed quantum MDS codes have different lengths from previous known results, and the minimum distances of all the q-ary quantum MDS codes are larger than q/2 + 1.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Hoa T. Bui, Guillermo Pineda-Villavicencio, Julien Ugon
Summary: The paper examines the linkedness of the graphs of cubical polytopes and proves that every cubical d-polytope has [d/2] and strong [d/2] linkedness, for every d = 3. These results are optimal for this class of polytopes.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Julia Carrigan, Isaiah Hollars, Eric Rowland
Summary: Two words p and q are avoided by the same number of length-n words, for all n, precisely when p and q have the same set of border lengths. Previous proofs of this theorem use generating functions but do not provide an explicit bijection. We give a bijective proof for all pairs p, q that have the same set of proper borders, establishing a natural bijection from the set of words avoiding p to the set of words avoiding q.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Luke Nelson, Kevin Treat
Summary: We define a poset called the Outer Tamari poset, which is shown to be isomorphic to a subposet of the Tamari lattice introduced by Pallo (1986) and further studied as the Comb poset by Csar, Sengupta, and Suksompong (2014). By using the Outer Tamari poset, we develop recursive formulas for the number of triangulations of the 3-dimensional cyclic polytopes. These triangulations can be considered as elements of both the higher Stasheff-Tamari orders in dimension three and the Tamari Block lattices defined in a previous article. Therefore, our work here can be seen as constructing recursive enumerations of these posets.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Nicholas A. Loehr, Gregory S. Warrington
Summary: This study explores variants of chromatic symmetric functions for rooted graphs and investigates the combinatorial identities and recursions satisfied by these rooted chromatic polynomials. It proves the irreducibility of Stanley's polynomial under certain conditions, establishes conditions for isomorphism of rooted trees as rooted graphs, and provides a combinatorial interpretation of the monomial expansion of pointed chromatic functions.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Shira Zerbib
Summary: This article studies the property of a family of sets and proves that when a family of compact convex sets has a specific intersection property, it can be pierced by a certain number of lines. The proofs are based on the topological KKM theorem.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
David Sossa, Vilmar Trevisan
Summary: The study focuses on the complementarity spectrum and separability index of graphs, demonstrating the relationship between the largest complementarity eigenvalues of graphs of a specific order and deducing the growth trend of the separability index of the set of connected graphs.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Anita Keszler, Zsolt Tuza
Summary: This study considers edge decompositions of K-v((3)) - I and provides decomposition results satisfying certain conditions, complementing previous research findings.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Ping Li
Summary: This paper explores the relationship between monochromatic connection coloring and the connectivity of a graph, providing a method and upper bounds for computing the monochromatic connection number. Additionally, the paper discusses the characteristics of MC-colorings for graphs with specific connectivity requirements.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Santiago Guzman-Pro
Summary: This article discusses the concepts of full-homomorphism, full H-colouring, and minimal H-obstruction. It proves the existence of a finite number of minimal H obstructions for every graph H. Furthermore, it describes the properties of minimal obstructions and poses some related questions.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Rongzhong Xiao
Summary: We prove that for any finite coloring of Q, there exist non-zero elements that satisfy certain conditions.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Robert Lukot'ka
Summary: The article studies the circular flow problem, gives the circular flow number of Goldberg snark G2k+1, and proves a conjecture.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Benjamin Egan, Yuri Nikolayevsky
Summary: A simple graph is called triangular if every edge of it belongs to a triangle. We conjecture that any graphical degree sequence all terms of which are greater than or equal to 4 has a triangular realisation, and establish this conjecture for a class of biregular graphical degree sequences.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Jakub Przybylo
Summary: We improve upon Molloy's breakthrough result by adapting Bernshteyn's proof, achieving a stronger result that states triangle-free graphs can be colored from lists of size (1 +o(1))A/ log A, where vertices sharing a common color do not induce a triangle in G. We also extend this result to graphs of maximum degree A by proving the sufficiency of list sizes (1000 + o(1))A/ log A, as implied by a more general result due to Amini and Reed. Furthermore, we demonstrate that lists of length 2(r - 2)A log2 log2 A/ log2 A are sufficient if one replaces the triangle with any Kr with r >= 4. All of these bounds hold in the context of correspondence colorings.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Hongwei Zhu, Minjia Shi
Summary: This paper studies the b-symbol weight hierarchy of Kasami codes and discusses their applications in high density data storage systems.
DISCRETE MATHEMATICS
(2024)