Search

In 2013, C. Godsil introduced the quantum version of Hedetniemi’s conjecture. To solve this conjecture, we introduce the concept of quantum multiplicative graph and obtain a necessary and sufficien...

The spectral radius (or the signless Laplacian spectral radius) of a general hypergraph is the maximum modulus of the eigenvalues of its adjacency (or its signless Laplacian) tensor. In this paper, we firstly obtain a lower bound of the spectral radius (or the signless Laplacian spectral radius) of general hypergraphs in terms of clique number. Moreover, we present a relation between a homogeneous polynomial and the clique number of general hypergraphs. As an application, we finally obtain an upper bound of the spectral radius of general hypergraphs in terms of clique number.

Let c ( G ) , g ( G ) , ω ( G ) and μ n − 1 ( G ) denote the number of components, the girth, the clique number and the second smallest Laplacian eigenvalue of the graph G, respectively. The strength η ( G ) and the fractional arboricity γ ( G ) are defined by η ( G ) = min F ⊆ E ( G ) ⁡ | F | c ( G − F ) − c ( G ) and γ ( G ) = max H ⊆ G ⁡ | E ( H ) | | V ( H ) | − 1 , where the optima are taken over all edge subsets F and all subgraphs H whenever the denominator is non-zero, respectively. Nash-Williams and Tutte proved that G has k edge-disjoint spanning trees if and only if η ( G ) ≥ k ; and Nash-Williams showed that G can be covered by at most k forests if and only if γ ( G ) ≤ k . In this paper, for integers r ≥ 2 , s and t, and any simple graph G of order n with minimum degree δ ≥ 2 s t and either clique number ω ( G ) ≤ r or girth g ≥ 3 , we prove that if μ n − 1 ( G ) > 2 s − 1 t φ ( δ , r ) or μ n − 1 ( G ) > 2 s − 1 t N ( δ , g ) , then η ( G ) ≥ s t , where φ ( δ , r ) = max ⁡ { δ + 1 , ⌊ r δ r − 1 ⌋ } and N ( δ , g ) is the Moore bound on the smallest possible number of vertices such that there exists a δ-regular simple graph with girth g. As corollaries, sufficient conditions on μ n − 1 ( G ) such that G has k edge-disjoint spanning trees are obtained. Analogous result involving μ n − 1 ( G ) to characterize fractional arboricity of graphs with given clique number is also presented. Former results in Liu et al. (2014) [17] and Hong et al. (2016) [11] are extended, and the result in Liu et al. (2019) [18] is improved.

Let $\kappa'(G)$, $\kappa(G)$, $\mu_{n-1}(G)$ and $\mu_1(G)$ denote the edge-connectivity, vertex-connectivity, the algebraic connectivity and the Laplacian spectral radius of $G$, respectively. In this paper, we prove that for integers $k\geq 2$ and $r\geq 2$, and any simple graph $G$ of order $n$ with minimum degree $\delta\geq k$, girth $g\geq 3$ and clique number $\omega(G)\leq r$, the edge-connectivity $\kappa'(G)\geq k$ if $\mu_{n-1}(G) \geq \frac{(k-1)n}{N(\delta,g)(n-N(\delta,g))}$ or if $\mu_{n-1}(G) \geq \frac{(k-1)n}{\varphi(\delta,r)(n-\varphi(\delta,r))}$, where $N(\delta,g)$ is the Moore bound on the smallest possible number of vertices such that there exists a $\delta$-regular simple graph with girth $g$, and $\varphi(\delta,r) = \max\{\delta+1,\lfloor\frac{r\delta}{r-1}\rfloor\}$. Analogue results involving $\mu_{n-1}(G)$ and $\frac{\mu_1(G)}{\mu_{n-1}(G)}$ to characterize vertex-connectivity of graphs with fixed girth and clique number are also presented. Former results in [Linear Algebra Appl. 439 (2013) 3777--3784], [Linear Algebra Appl. 578 (2019) 411--424], [Linear Algebra Appl. 579 (2019) 72--88], [Appl. Math. Comput. 344-345 (2019) 141--149] and [Electronic J. Linear Algebra 34 (2018) 428--443] are improved or extended., Comment: 14 pages

In this paper we show that it can be decided in polynomial time whether or not the visibility graph of a given point set is 4-colourable, and such a 4-colouring, if it exists, can also be constructed in polynomial time. We show that the problem of deciding whether the visibility graph of a point set is 5-colourable, is NP-complete. We give an example of a point visibility graph that has chromatic number 6 while its clique number is only 4.

A γ-quasi-clique in a simple undirected graph refers to a subset of vertices that induces a subgraph with edge density at least γ. When γ equals one, this definition corresponds to a classical clique. When γ is less than one, it relaxes the requirement of all possible edges by the clique definition. Quasi-clique detection has been used in graph-based data mining to find dense clusters, especially in large-scale error-prone data sets in which the clique model can be overly restrictive. The maximum γ-quasi-clique problem, seeking a γ-quasi-clique of maximum cardinality in the given graph, can be formulated as an optimization problem with a linear objective function and a single quadratic constraint in binary variables. This article investigates the Lagrangian dual of this formulation and develops an upper-bounding technique using the geometry of ellipsoids to bound the Lagrangian dual. The tightness of the upper bound is compared with those obtained from multiple mixed-integer programming formulations of the problem via experiments on benchmark instances.

A signed relative clique number of signed graph (where edges are assigned positive or negative signs) is the size of a largest subset X of vertices such that every two vertices are either adjacent or are part of a 4-cycle with an odd number of negative edges. The signed relative clique number is sandwiched between two other parameters of signed graphs, namely, the signed absolute clique number and the signed chromatic number, all three notions defined in Naserasr et al. (2014). Thus, together with a result from Ochem et al. (2016) the lower bound of 8 and upper bound of 40 has already been proved for the signed relative clique number of the family of planar graphs. Here we improve the upper bound to 15. Furthermore, we determine the exact values of signed relative clique number of the families of outerplanar graphs and triangle-free planar graphs.

The notions of critical ideals and characteristic ideals of graphs are introduced by Corrales and Valencia to study properties of graphs, including clique number, zero forcing number, minimum rank and critical group. In this paper, we provide methods to compute critical ideals of complete multipartite graphs and obtain complete answers for the characteristic ideals of complete multipartite graphs.

Let R be an unital ring which is not necessarily commutative. The intersection graph of ideals of R is a graph with the vertex set which contains proper ideals of R and distinct two vertices I and ...

It is shown that a finite-dimensional formally real simple Jordan algebra is completely determined by the relation of Jordan-orthogonality.Communicated by Prof. Alberto Elduque

Let G be a finite group, and let cd ( G ) denote the set of degrees of the irreducible complex characters of G . The degree graph Δ ( G ) of G is defined as the simple undirected graph whose vertex set V ( G ) consists of the prime divisors of the numbers in cd ( G ) , two distinct vertices p and q being adjacent if and only if pq divides some number in cd ( G ) . In this note, we provide an upper bound on the size of V ( G ) in terms of the clique number ω ( G ) (i.e., the maximum size of a subset of V ( G ) inducing a complete subgraph) of Δ ( G ) . Namely, we show that | V ( G ) | ≤ max { 2 ω ( G ) + 1 , 3 ω ( G ) − 4 } . Examples are given in order to show that the bound is best possible. This completes the analysis carried out in [1] where the solvable case was treated, extends the results in [3] , [4] , [9] , and answers a question posed by the first author and H.P. Tong-Viet in [4] .

We prove a conjecture of Andras Gyarfas, that for all κ , l , every graph with clique number at most κ and sufficiently large chromatic number has an odd hole of length at least l.

For a simple graph $G(V,E)$ with $n$ vertices, $m$ edges, vertex set $V(G)=\{v_1, v_2, \dots, v_n\}$ and edge set $E(G)=\{e_1, e_2,\dots, e_m\}$, the adjacency matrix $A=(a_{ij})$ of $G$ is a $(0, 1)$-square matrix of order $n$ whose $(i,j)$-entry is equal to 1 if $v_i$ is adjacent to $v_j$ and equal to 0, otherwise. Let $D(G)={diag}(d_1, d_2, \dots, d_n)$ be the diagonal matrix associated to $G$, where $d_i=\deg(v_i),$ for all $i\in \{1,2,\dots,n\}$. The matrices $L(G)=D(G)-A(G)$ and $Q(G)=D(G)+A(G)$ are respectively called the Laplacian and the signless Laplacian matrices and their spectra (eigenvalues) are respectively called the Laplacian spectrum ($L$-spectrum) and the signless Laplacian spectrum ($Q$-spectrum) of the graph $G$. If $0=\mu_n\leq\mu_{n-1}\leq\cdots\leq\mu_1$ are the Laplacian eigenvalues of $G$, Brouwer conjectured that the sum of $k$ largest Laplacian eigenvalues $S_{k}(G)$ satisfies $S_{k}(G)=\sum\limits_{i=1}^{k}\mu_i\leq m+{k+1 \choose 2}$ and this conjecture is still open. If $q_1,q_2, \dots, q_n$ are the signless Laplacian eigenvalues of $G$, for $1\leq k\leq n$, let $S^{+}_{k}(G)=\sum_{i=1}^{k}q_i$ be the sum of $k$ largest signless Laplacian eigenvalues of $G$. Analogous to Brouwer's conjecture, Ashraf et al. conjectured that $S^{+}_{k}(G)\leq m+{k+1 \choose 2}$, for all $1\leq k\leq n$. This conjecture has been verified in affirmative for some classes of graphs. We obtain the upper bounds for $S^{+}_{k}(G)$ in terms of the clique number $\omega$, the vertex covering number $\tau$ and the diameter of the graph $G$. Finally, we show that the conjecture holds for large families of graphs.

We study distance graphs with exponentially large chromatic number which do not contain cliques of prescribed size in the rational space.

Considering connected K 1 , 3 -free graphs with independence number at least 3, Chudnovsky and Seymour (2010) showed that every such graph, say G , is 2 ω -colourable where ω denotes the clique number of G . We study ( K 1 , 3 , Y ) -free graphs, and show that the following three statements are equivalent. • [(1)] Every connected ( K 1 , 3 , Y ) -free graph which is distinct from an odd cycle and which has independence number at least 3 is perfect. • [(2)] Every connected ( K 1 , 3 , Y ) -free graph which is distinct from an odd cycle and which has independence number at least 3 is ω -colourable. • [(3)] Y is isomorphic to an induced subgraph of P 5 or Z 2 (where Z 2 is also known as hammer). Furthermore, for connected ( K 1 , 3 , Y ) -free graphs (without an assumption on the independence number), we show a similar characterisation featuring the graphs P 4 and Z 1 (where Z 1 is also known as paw).

A hole is an induced cycle of length at least 4, and a cap is obtained from a hole by adding a new vertex and joining it to exactly two adjacent vertices of the hole. Let G be a graph containing neither caps nor holes of even lengths as induced subgraphs. Cameron et al. (2018) showed that χ ( G ) ≤ ⌊ 3 ω ( G ) 2 ⌋ , and asked whether χ ( G ) ≤ ⌈ 5 ω ( G ) 4 ⌉ , where χ ( G ) and ω ( G ) denote the chromatic number and clique number of G , respectively. In this paper, we show that χ ( G ) ≤ ⌈ 4 ω ( G ) 3 ⌉ , and χ ( G ) ≤ ⌈ 5 ω ( G ) 4 ⌉ if G further has no 5-cycles sharing exactly one edge. This improves the conclusion of Cameron et al. (2018), and conditionally answers their question in affirmative.

Fix an oriented graph H , and let G be a graph with bounded clique number and very large chromatic number. If we somehow orient its edges, must there be an induced subdigraph isomorphic to H ? Kierstead and Rodl (1996) raised this question for two specific kinds of digraph H : the three-edge path, with the first and last edges both directed towards the interior; and stars (with many edges directed out and many directed in). Aboulker et al. (2018) subsequently conjectured that the answer is affirmative in both cases. We give affirmative answers to both questions.

Very recently, Aouchiche and Hansen gave an upper bound on the ratio of G A ∕ χ of the geometric–arithmetic index G A ( G ) and the chromatic number χ ( G ) of a graph. Furthermore, they proposed several conjectures on the relation between geometric–arithmetic index and chromatic number, and clique number. In this note, we disprove four of those conjectures. In addition, we present a sufficient condition for an edge e ∈ E ( G ) with G A ( G − e ) G A ( G ) .

We obtain lower and upper bounds on general multiplicative Zagreb indices for graphs of given clique number and order. Bounds on the basic multiplicative Zagreb indices and on the multiplicative sum Zagreb index follow from our results. We also determine graphs with the smallest and the largest indices.

We prove that every triangle-free graph with maximum degree $\Delta$ has list chromatic number at most $(1+o(1))\frac{\Delta}{\ln \Delta}$. This matches the best-known bound for graphs of girth at least 5. We also provide a new proof that for any $r\geq 4$ every $K_r$-free graph has list-chromatic number at most $200r\frac{\Delta\ln\ln\Delta}{\ln\Delta}$., Comment: Revised according to referee reports

A graph G with clique number $$\omega (G)$$ and chromatic number $$\chi (G)$$ is perfect if $$\chi (H)=\omega (H)$$ for every induced subgraph H of G. A family $${\mathcal {G}}$$ of graphs is called $$\chi $$ -bounded with binding function f if $$\chi (G') \le f(\omega (G'))$$ holds whenever $$G \in {\mathcal {G}}$$ and $$G'$$ is an induced subgraph of G. In this paper we will present a survey on polynomial $$\chi $$ -binding functions. Especially we will address perfect graphs, hereditary graphs satisfying the Vizing bound ( $$\chi \le \omega +1$$ ), graphs having linear $$\chi $$ -binding functions and graphs having non-linear polynomial $$\chi $$ -binding functions. Thereby we also survey polynomial $$\chi $$ -binding functions for several graph classes defined in terms of forbidden induced subgraphs, among them $$2K_2$$ -free graphs, $$P_k$$ -free graphs, claw-free graphs, and $${ diamond}$$ -free graphs. ( [])

For a simple graph G with order n and size m having Laplacian eigenvalues $$\mu _1, \mu _2, \dots , \mu _{n-1},\mu _n=0$$ , let $$S_k(G)=\sum _{i=1}^{k}\mu _i$$ , be the sum of k largest Laplacian eigenvalues of G. We obtain upper bounds for the sum of k largest Laplacian eigenvalues of two large families of graphs. As a consequence, we prove Brouwer’s Conjecture for large number of graphs which belong to these families of graphs.

Graph defined by Birkhoff–James orthogonality relation in normed spaces is studied. It is shown that (i) in a normed space of sufficiently large dimension there always exists a nonzero vector which is mutually Birkhoff–James orthogonal to each among a fixed number of given vectors, and (ii) in nonsmooth norms the cardinality of the set of pairwise Birkhoff–James orthogonal vectors may exceed the dimension of the vector space, but this cardinality is always bounded above by a function of the dimension. It is further shown that any given pair of elements in a normed space can be extended to a finite tuple such that each consecutive elements are mutually Birkhoff–James orthogonal; the exact minimal length of the tuple is also determined.

In this paper, we first introduce a new graph Γ N over an extension N of semigroups and after that we study and characterize the spectral properties such as the diameter, girth, maximum and minimum degrees, domination number, chromatic number, clique number, degree sequence, irregularity index, and also perfectness for Γ N . Moreover, we state and prove some important known Zagreb indices on this new graph.

Random geometric graphs have become now a popular object of research. Defined rather simply, these graphs describe real networks much better than classical Erdős–Rényi graphs due to their ability to produce tightly connected communities. The n vertices of a random geometric graph are points in d-dimensional Euclidean space, and two vertices are adjacent if they are close to each other. Many properties of these graphs have been revealed in the case when d is fixed. However, the case of growing dimension d is practically unexplored. This regime corresponds to a real-life situation when one has a data set of n observations with a significant number of features, a quite common case in data science today. In this paper, we study the clique structure of random geometric graphs when $$n\rightarrow \infty$$ n → ∞ , and $$d \rightarrow \infty$$ d → ∞ , and average vertex degree grows significantly slower than n. We show that under these conditions, random geometric graphs do not contain cliques of size 4 a. s. if only $$d \gg \log ^{1 + \epsilon } n$$ d ≫ log 1 + ϵ n . As for the cliques of size 3, we present new bounds on the expected number of triangles in the case $$\log ^2 n \ll d \ll \log ^3 n$$ log 2 n ≪ d ≪ log 3 n that improve previously known results. In addition, we provide new numerical results showing that the underlying geometry can be detected using the number of triangles even for small n.

Let $\omega(G)$ and $\chi(G)$ denote the clique number and chromatic number of a graph $G$, respectively. The {\em disjointness graph} of a family of curves (continuous arcs in the plane) is the graph whose vertices correspond to the curves and in which two vertices are joined by an edge if and only if the corresponding curves are disjoint. A curve is called {\em $x$-monotone} if every vertical line intersects it in at most one point. An $x$-monotone curve is {\em grounded} if its left endpoint lies on the $y$-axis. We prove that if $G$ is the disjointness graph of a family of grounded $x$-monotone curves such that $\omega(G)=k$, then $\chi(G)\leq \binom{k+1}{2}$. If we only require that every curve is $x$-monotone and intersects the $y$-axis, then we have $\chi(G)\leq \frac{k+1}{2}\binom{k+2}{3}$. Both of these bounds are best possible. The construction showing the tightness of the last result settles a 25 years old problem: it yields that there exist $K_k$-free disjointness graphs of $x$-monotone curves such that any proper coloring of them uses at least $\Omega(k^{4})$ colors. This matches the upper bound up to a constant factor., Comment: 21 pages, 5 figures

We study the asymptotic behavior of the clique number in rank-1 inhomogeneous random graphs, where edge probabilities between vertices are roughly proportional to the product of their vertex weights. We show that the clique number is concentrated on at most two consecutive integers, for which we provide an expression. Interestingly, the order of the clique number is primarily determined by the overall edge density, with the inhomogeneity only affecting multiplicative constants or adding at most a $\log\log(n)$ multiplicative factor. For sparse enough graphs the clique number is always bounded and the effect of inhomogeneity completely vanishes., 29 pages

We study structural properties of graphs with bounded clique number and high minimum degree. In particular, we show that there exists a function L = L(r,ɛ) such that every Kr-free graph G on n vertices with minimum degree at least ((2r–5)/(2r–3)+ɛ)n is homomorphic to a Kr-free graph on at most L vertices. It is known that the required minimum degree condition is approximately best possible for this result.For r = 3 this result was obtained by Łuczak (2006) and, more recently, Goddard and Lyle (2011) deduced the general case from Łuczak’s result. Łuczak’s proof was based on an application of Szemerédi’s regularity lemma and, as a consequence, it only gave rise to a tower-type bound on L(3, ɛ). The proof presented here replaces the application of the regularity lemma by a probabilistic argument, which yields a bound for L(r, ɛ) that is doubly exponential in poly(ɛ).

For a graph G without isolated vertices, the inverse degree of a graph G is defined as I D ( G ) = &sum, u &isin, V ( G ) d ( u ) - 1 where d ( u ) is the number of vertices adjacent to the vertex u in G. By replacing - 1 by any non-zero real number we obtain zeroth-order general Randić index, i.e., 0 R &gamma, ( G ) = &sum, V ( G ) d ( u ) &gamma, where &gamma, &isin, R - { 0 } . Xu et. al. investigated some lower and upper bounds on I D for a connected graph G in terms of connectivity, chromatic number, number of cut edges, and clique number. In this paper, we extend their results and investigate if the same results hold for &gamma, &lt, 0 . The corresponding extremal graphs have also been identified.

Treewidth is an important graph invariant, relevant for both structural and algorithmic reasons. A necessary condition for a graph class to have bounded treewidth is the absence of large cliques. We study graph classes in which this condition is also sufficient, which we call \((\text {tw},\omega )\)-bounded. Such graph classes are known to have useful algorithmic applications related to variants of the clique and k-coloring problems. We consider six well-known graph containment relations: the minor, topological minor, subgraph, induced minor, induced topological minor, and induced subgraph relations. For each of them, we give a complete characterization of the graphs H for which the class of graphs excluding H is \((\text {tw},\omega )\)-bounded. Our results imply that the class of 1-perfectly orientable graphs is \((\text {tw},\omega )\)-bounded, answering a question of Bresar, Hartinger, Kos, and Milanic from 2018. We also reveal some further algorithmic implications of \((\text {tw},\omega )\)-boundedness related to list k-coloring and clique problems.

A remarkable connection between the clique number and the Lagrangian of a graph was established by Motzkin and Straus. Later, Rota Bulo and Pelillo extended the theorem of Motzkin-Straus to r-uniform hypergraphs by studying the relation of local (global) minimizers of a homogeneous polynomial function of degree r and the maximal (maximum) cliques of an r-uniform hypergraph. In this paper, we study polynomial optimization problems for non-uniform hypergraphs with four different types of edges and apply it to get an upper bound of Turan densities of complete non-uniform hypergraphs.

We consider several extremal problems of maximizing the number of colorings and independent sets in some graph families with fixed chromatic number and order. First, we address the problem of maximizing the number of colorings in the family of connected graphs with chromatic number k and order n where $$k\ge 4$$ . It was conjectured that extremal graphs are those which have clique number k and size $${k\atopwithdelims ()2}+n-k$$ . We affirm this conjecture for 4-chromatic claw-free graphs and for all k-chromatic line graphs with $$k\ge 4$$ . We also reduce this extremal problem to a finite family of graphs when restricted to claw-free graphs. Secondly, we determine the maximum number of independent sets of each size in the family of n-vertex k-chromatic graphs (respectively connected n-vertex k-chromatic graphs and n-vertex k-chromatic graphs with c components). We show that the unique extremal graph is $$K_k\cup E_{n-k}$$ , $$K_1\vee (K_{k-1}\cup E_{n-k})$$ and $$(K_1 \vee (K_{k-1} \cup E_{n-k-c+1}))\cup E_{c-1}$$ respectively.

Let G be a graph with adjacency matrix A ( G ) and let D ( G ) be the diagonal matrix of the degrees of G. For any real α ∈ [ 0 , 1 ] , Nikiforov [3] defined the matrix A α ( G ) as A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . The largest eigenvalue of A α ( G ) is called the A α -spectral radius of G. In this paper, we give three edge graft transformations on A α -spectral radius. As applications, we determine the unique graph with maximum A α -spectral radius among all connected graphs with diameter d, and determine the unique graph with minimum A α -spectral radius among all connected graphs with given clique number. In addition, some bounds on the A α -spectral radius are obtained.

A k - γ c -critical graph is a graph G with connected domination number γ c ( G ) = k and γ c ( G + u v ) k for any pair of non-adjacent vertices u and v of G . Let ω and α be respectively the clique number and the independence number of a graph. In this paper, we prove that every k - γ c -critical graph satisfies α + ω ≤ n − ⌊ k 2 ⌋ + 1 for 1 ≤ k ≤ 3 . We also characterize all 3 - γ c -critical graphs achieving the upper bound. For k ≥ 4 , we show that there are infinitely many k - γ c -critical graphs satisfying α + ω = n − ⌊ k 2 ⌋ + 1 . Thus, we conclude this paper with an open problem that every k - γ c -critical graph for k ≥ 4 satisfies α + ω ≤ n − ⌊ k 2 ⌋ + 1 .

An oriented graph is a directed graph with no directed cycle of length one or two. The relative clique number of an oriented graph is the cardinality of a largest subset X of vertices such that each pair of vertices is either adjacent or connected by a directed 2-path. It is known that the oriented relative clique number of a planar graph is at most 80. Here we improve the upper bound to 32. We also prove an upper bound of 14 for oriented relative clique number of triangle-free planar graphs. Furthermore, we determine the exact values of oriented relative clique number for the families of outerplanar graphs with girth at least g and planar graphs with girth at least g + 2 for all g ≥ 3 . Moreover, we study the relation of oriented relative clique number with oriented chromatic number, oriented absolute clique number and maximum degree of a graph. We also show that oriented relative clique number of a connected subcubic graph is at most seven which weakly supports a conjecture by Sopena (JGT 1997).

In this paper, we first show that every ( $$P_6$$ , diamond, $$K_4$$ )-free graph is 6-colorable. We also give an example of a ( $$P_6$$ , diamond, $$K_4$$ )-free graph G with $$\chi (G)$$ $$ = 6$$ . Further, we show that for every ( $$P_6$$ , diamond)-free graph G, the chromatic number of G is upper bounded by a linear function of its clique number. This generalizes some known results in the literature.

Let C 4 ( n ) be the family of all connected 4 -chromatic graphs of order n . Given an integer x ≥ 4 , we consider the problem of finding the maximum number of x -colorings of a graph in C 4 ( n ) . It was conjectured that the maximum number of x -colorings is equal to ( x ) ↓ 4 ( x − 1 ) n − 4 and the extremal graphs are those which have clique number 4 and size n + 2 . In this article, we reduce this problem to a finite family of graphs. We show that there exists a finite family F of connected 4 -chromatic graphs such that if the number of x -colorings of every graph G in F is less than ( x ) ↓ 4 ( x − 1 ) | V ( G ) | − 4 then the conjecture holds to be true.

For a simple graph G of order n, size m and with signless Laplacian eigenvalues q 1 , q 2 , … , q n , the signless Laplacian energy Q E ( G ) is defined as Q E ( G ) = ∑ i = 1 n | q i − d ‾ | , where d ‾ = 2 m n is the average vertex degree of G. We obtain the lower bounds for Q E ( G ) , in terms of first Zagreb index M 1 ( G ) , maximum degree d 1 , second maximum degree d 2 , minimum degree d n and second minimum degree d n − 1 . As a consequence of these bounds, we obtain several bounds for the energy E ( L ( G ) ) of the line graph L ( G ) of graph G in terms of various graph parameters like M 1 ( G ) , ω (the clique number), n, m, etc., which improve some recently known bounds.

We investigate the generalized bilinear forms graph Γ d over a residue class ring Z p s . The graph Γ d is a connected vertex-transitive graph, and we completely determine its independence number, clique number, chromatic number and maximum cliques. We also prove that cores of both Γ d and its complement are maximum cliques. The graph Γ d is useful for error-correcting codes. We show that there is a largest independent set of Γ d which is a linear MRD code over Z p s .

We consider a class of graphs G(n, r, s) = (V (n, r),E(n, r, s)) defined as follows: $$V(n,r) = \{ x = ({x_{1,}},{x_2}...{x_n}):{x_i} \in \{ 0,1\} ,{x_{1,}} + {x_2} + ... + {x_n} = r\} ,E(n,r,s) = \{ \{ x,y\} :(x,y) = s\} $$ where (x, y) is the Euclidean scalar product. We study random subgraphs G(G(n, r, s), p) with edges independently chosen from the set E(n, r, s) with probability p each. We find nontrivial lower and upper bounds on the clique number of such graphs.

For a simple graph G with n vertices and m edges having Laplacian eigenvalues μ 1 ( G ) ≥ μ 2 ( G ) ≥ ⋯ ≥ μ n ( G ) , let S k ( G ) be the sum of k largest Laplacian eigenvalues of G . In this note, we prove that if G is a connected graph of order n ≥ 2 with m edges having clique number ω and vertex covering number τ , then S k ( G ) ≤ k ( τ + 1 ) + m − ω ( ω − 1 ) 2 , with equality if k ≤ ω − 1 and G is the graph obtained by joining n − ω pendant vertices with one of the vertices in K ω . Our work improves a recent work of Ganie et al.

Let D be a finite and simple digraph with vertex set V ( D ) . For a vertex v ∈ V ( D ) , the degree d ( v ) of v is defined as the minimum value of its out-degree d + ( v ) and its in-degree d − ( v ) . If D is a graph or a digraph with minimum degree δ and edge-connectivity λ , then λ ≤ δ . A graph or a digraph is maximally edge-connected if λ = δ . A graph or a digraph is called super-edge-connected if every minimum edge-cut consists of edges adjacent to or from a vertex of minimum degree. In this note we present degree sequence conditions for maximally edge-connected and super-edge-connected digraphs depending on the clique number of the underlying graph.

The class of $$2K_{2}$$ -free graphs and its various subclasses have been studied in a variety of contexts. In this paper, we are concerned with the colouring of $$(P_{3}\cup P_{2})$$ -free graphs, a super class of $$2K_{2}$$ -free graphs. We derive a $$O(\omega ^{3})$$ upper bound for the chromatic number of $$(P_{3} \cup P_{2})$$ -free graphs, and sharper bounds for $$(P_{3} \cup P_{2}$$ , diamond)-free graphs and for $$(2K_{2},$$ diamond)-free graphs, where $$\omega $$ denotes the clique number. The last two classes are perfect if $$\omega \ge 5$$ and $$\ge 4$$ respectively.

The packing chromatic number $$\chi _{\rho }(G)$$ of a graph G is the smallest integer k such that the vertex set of G can be partitioned into sets $$V_i$$ , $$i\in [k]$$ , where each $$V_i$$ is an i-packing. In this paper, we investigate for a given triple (a, b, c) of positive integers whether there exists a graph G such that $$\omega (G) = a$$ , $$\chi (G) = b$$ , and $$\chi _{\rho }(G) = c$$ . If so, we say that (a, b, c) is realizable. It is proved that $$b=c\ge 3$$ implies $$a=b$$ , and that triples $$(2,k,k+1)$$ and $$(2,k,k+2)$$ are not realizable as soon as $$k\ge 4$$ . Some of the obtained results are deduced from the bounds proved on the packing chromatic number of the Mycielskian. Moreover, a formula for the independence number of the Mycielskian is given. A lower bound on $$\chi _{\rho }(G)$$ in terms of $$\Delta (G)$$ and $$\alpha (G)$$ is also proved.

A star coloring of an undirected graph G is a coloring of the vertices of G such that (i) no two adjacent vertices receive the same color, and (ii) no path on four vertices (not necessarily induced) is bi-colored. The star chromatic number of G, denoted by $$\chi _s(G)$$ , is the minimum number of colors needed to star color G. Similar to the notion of $$\chi $$ -boundedness in graphs, we say that a hereditary class of graphs $$\mathcal {G}$$ is $$\chi _s$$ -bounded if, for some integer valued function f, $$\chi _s(G) \le f(\omega (G))$$ for every $$G \in \mathcal {G}$$ , where $$\omega (G)$$ is the maximum number of vertices that are pairwise adjacent in G. We show that some classes of perfect graphs, some classes of ( $$P_5, C_4$$ )-free graphs, and some classes of $$K_{1, 3}$$ -free graphs are $$\chi _s$$ -bounded. We also give examples in most of the cases to show that the bounds are tight.

In this note, we introduce a new method for constructing graphs with high chromatic number and small clique. Indeed, via this method, we present a new proof for the well-known Kneser's conjecture.

For a simple graph G with n -vertices, m edges and having signless Laplacian eigenvalues q 1 , q 2 , … , q n , the signless Laplacian energy Q E ( G ) of the graph G is defined as Q E ( G ) = ∑ i = 1 n ∣ q i − d ¯ ∣ , where d ¯ = 2 m n is the average degree of G . In this paper, we obtain the lower and upper bounds for the signless Laplacian energy Q E ( G ) in terms of clique number ω , maximum degree Δ , number of vertices n , first Zagreb index M 1 ( G ) and number of edges m . As an application, we obtain the bounds for the energy of line graph ℒ ( G ) of a graph G in terms of various graph parameters. We also obtain a relation between the signless Laplacian energy Q E ( G ) and the incidence energy I E ( G ) .

In 1998, Reed conjectured that every graph $G$ satisfies $\chi(G) \leq \lceil \frac{1}{2}(\Delta(G) + 1 + \omega(G))\rceil$, where $\chi(G)$ is the chromatic number of $G$, $\Delta(G)$ is the maximum degree of $G$, and $\omega(G)$ is the clique number of $G$. As evidence for his conjecture, he proved an "epsilon version" of it, i.e. that there exists some $\varepsilon > 0$ such that $\chi(G) \leq (1 - \varepsilon)(\Delta(G) + 1) + \varepsilon\omega(G)$. It is natural to ask if Reed's conjecture or an epsilon version of it is true for the list-chromatic number. In this paper we consider a "local version" of the list-coloring version of Reed's conjecture. Namely, we conjecture that if $G$ is a graph with list-assignment $L$ such that for each vertex $v$ of $G$, $|L(v)| \geq \lceil \frac{1}{2}(d(v) + 1 + \omega(v))\rceil$, where $d(v)$ is the degree of $v$ and $\omega(v)$ is the size of the largest clique containing $v$, then $G$ is $L$-colorable. Our main result is that an "epsilon version" of this conjecture is true, under some mild assumptions. Using this result, we also prove a significantly improved lower bound on the density of $k$-critical graphs with clique number less than $k/2$, as follows. For every $\alpha > 0$, if $\varepsilon \leq \frac{\alpha^2}{1350}$, then if $G$ is an $L$-critical graph for some $k$-list-assignment $L$ such that $\omega(G) < (\frac{1}{2} - \alpha)k$ and $k$ is sufficiently large, then $G$ has average degree at least $(1 + \varepsilon)k$. This implies that for every $\alpha > 0$, there exists $\varepsilon > 0$ such that if $G$ is a graph with $\omega(G)\leq (\frac{1}{2} - \alpha)\mathrm{mad}(G)$, where $\mathrm{mad}(G)$ is the maximum average degree of $G$, then $\chi_\ell(G) \leq \left\lceil (1 - \varepsilon)(\mathrm{mad}(G) + 1) + \varepsilon \omega(G)\right\rceil$., Comment: This version corrects some mistakes in Section 3 (see Remark 1 on page 11) -- all results in Section 1 still hold. Corrigendum to appear in JCTB

A total-colored path is total rainbow if its edges and internal vertices have distinct colors. A total-colored graph G is total rainbow connected if any two distinct vertices are connected by some total rainbow path. The total rainbow connection number of G, denoted by trc(G), is the smallest number of colors required to color the edges and vertices of G in order to make G total rainbow connected. In this paper, we investigate graphs with small total rainbow connection number. First, for a connected graph G, we prove that $${\text{trc(G) = 3 if}}\left( {\begin{array}{*{20}{c}} {n - 1} \\ 2 \end{array}} \right) + 1 \leqslant \left| {{\text{E(G)}}} \right| \leqslant \left( {\begin{array}{*{20}{c}} n \\ 2 \end{array}} \right) - 1$$ , and $${\text{trc(G)}} \leqslant {\text{6 if }}\left| {{\text{E(G)}}} \right| \geqslant \left( {\begin{array}{*{20}{c}} {n - 2} \\ 2 \end{array}} \right) + 2$$ . Next, we investigate the total rainbow connection numbers of graphs G with |V(G)| = n, diam(G) ≥ 2, and clique number ω(G) = n − s for 1 ≤ s ≤ 3. In this paper, we find Theorem 3 of [Discuss. Math. Graph Theory, 2011, 31(2): 313–320] is not completely correct, and we provide a complete result for this theorem.