For 0≤α≤1, the Aα-matrix of graph G is defined asAα(G)=αD(G)+(1−α)A(G), where D(G) and A(G) are the diagonal matrix of the degrees and the adjacency matrix of G, respectively. On the premise of a ...fixed number of edges, Zhai et al. (2020) 15 depicted the extremal graph which has the largest A12-spectral radius, and also characterized the graph maximizing the A12-spectral radius among all graphs with given clique number (respectively, chromatic number). In this paper, we extend the conclusion of them to Aα-spectral radius for α∈12,1.
Given a positive integer t, let Pt and Kt respectively denote the chordless path and the complete graph on t vertices. For a graph G, let χ(G) and ω(G) respectively denote the chromatic number and ...clique number of G. It is known that every (P5,K4)-free graph G satisfies χ(G)≤5, and the bound is tight. A flag is the graph obtained from a K4 by attaching a pendent vertex. Clearly, the class of flag-free graphs generalizes the class of K4-free graphs. In this paper, we show the following:•Every (P5,flag,K5)-free graph G that contains a K4 satisfies χ(G)≤8.•Every (P5,flag,K6)-free graph G satisfies χ(G)≤8.•Every (P5,flag,K7)-free graph G satisfies χ(G)≤9. We also give examples to show that the given bounds are tight. Further, we show that every (P5, flag)-free graph G with ω(G)≥4 satisfies χ(G)≤max{8,2ω(G)−3}, and the bound is tight for ω(G)∈{4,5,6}. We note that our bound is an improvement over that given in Dong et al. 3,4.
Graph theory can give a representation of abstract mathematical systems such as groups or rings. We have many graph representations for a group, in this study we use the coprime graph representation ...for a generalized quaternion group to find the numerical invariants of the graph, which are the clique number and the chromatic number. The main results obtained from this study are the clique number of the coprime graph representation for the generalized quaternion group is equal to the chromatic number of the coprime graph representation for the generalized quaternion group for each case of the order.
Let G be a simple graph with n vertices, m edges, maximum degree Δ, average degree d‾=2mn, clique number ω having Laplacian eigenvalues μ1,μ2,…,μn−1,μn=0. For k (1≤k≤n), let Sk(G)=∑i=1kμi and let σ ...(1≤σ≤n−1) be the number of Laplacian eigenvalues greater than or equal to average degree d‾. In this paper, we obtain a lower bound for Sω−1(G) and an upper bound for Sσ(G) in terms of m, Δ, σ and clique number ω of the graph. As an application, we obtain the stronger bounds for the Laplacian energy LE(G)=∑i=1n|μi−d‾|, which improve some well known earlier bounds.
For a graph G, let χ(G) and ω(G), respectively, denote the chromatic number and clique number of G. We give an explicit structural description of (P5, gem)‐free graphs, and show that every such graph ...G satisfies χ(G)≤⌈5ω(G)4⌉. Moreover, this bound is best possible. Here a gem is the graph that consists of an induced four‐vertex path plus a vertex which is adjacent to all the vertices of that path.
The greedy coloring algorithm shows that a graph of maximum degree at most Δ has chromatic number at most Δ+1, and this is tight for cliques. Much attention has been devoted to improving this “greedy ...bound” for graphs without large cliques. Brooks famously proved that this bound can be improved by one if Δ≥3 and the graph contains no clique of size Δ+1. Reed's Conjecture states that the “greedy bound” can be improved by k if the graph contains no clique of size Δ+1−2k. Johansson proved that the “greedy bound” can be improved by a factor of Ω(ln(Δ)−1) or Ω(ln(ln(Δ))ln(Δ)) for graphs with no triangles or no cliques of any fixed size, respectively.
Notably missing is a linear improvement on the “greedy bound” for graphs without large cliques. In this paper, we prove that for sufficiently large Δ, if G is a graph with maximum degree at most Δ and no clique of size ω, thenχ(G)≤72Δln(ω)ln(Δ). This implies that for sufficiently large Δ, if ω(72c)2≤Δ then χ(G)≤Δ/c.
This bound actually holds for the list-chromatic and even the correspondence chromatic number (also known as DP-chromatic number). In fact, we prove what we call a “local version” of it, a result implying the existence of a coloring when the number of available colors for each vertex depends on local parameters, like the degree and the clique number of its neighborhood. We prove that for sufficiently large Δ, if G is a graph of maximum degree at most Δ and minimum degree at least ln2(Δ) with list-assignment L, then G is L-colorable if for each v∈V(G),|L(v)|≥72deg(v)⋅min{ln(ω(v))ln(deg(v)),ω(v)ln(ln(deg(v)))ln(deg(v)),log2(χ(v)+1)ln(deg(v))}, where χ(v) denotes the chromatic number of the neighborhood of v and ω(v) denotes the size of a largest clique containing v. This simultaneously implies the linear improvement over the “greedy bound” and the two aforementioned results of Johansson.
The exact distance p-power of a graph G, denoted G#p, is a graph on vertex set V(G) in which two vertices are adjacent if they are at distance exactly p in G. Given integers k and p, we define f(k, ...p) to be the maximum possible order of a clique in the exact distance p-powers of graphs with maximum degree k + 1. It is easily observed that f(k, 2) ≤ k2 + k + 1. We prove that equality may only hold if a connected component of G is isomorphic to a member of the class Pk of incidence graphs of finite projective k-geometries. (These famous combinatorial structures are known to exist when k is a prime power, and are conjectured not to exist for other values of k.) We then study the case of graphs of maximum degree k + 1 with clique number k2 + k. One way to obtain such a graph is to remove a vertex from a graph in Pk; we call Pk' the class of all such resulting graphs. We prove that for any graph G of maximum degree k + 1 whose exact square has a (k2 + k)-clique, either G has a subgraph isomorphic to a graph in P’k, or a connected component of G is a (k + 1)-regular bipartite graph of order 2(k2 + k). We call Ok the class of such bipartite graphs, and study their structural properties. These properties imply that (if they exist) the graphs in Ok must be highly symmetric. Using this structural information, we show that O2 contains only one graph, known as the Franklin graph. We then show that O3 also consists of a single graph, which we build. Furthermore, we show that O4 and O5 are empty.
For general values of p, we prove that f(k, p) ≤ (k + 1)kp/2 + 1, and that the bound is tight for every odd integer p ≥ 3. This implies that f(k, 2) = f(k, 3) whenever there exists a finite projective k-geometry, however, in such a case, the bound of f(k, 3) could also be reached by highly symmetric graphs built from a finite k-geometry, which is not the case for other values of k.
A hereditary class G of graphs is χ-bounded if there is a χ-binding function, say f such that χ(G)≤f(ω(G)), for every G∈G, where χ(G) (ω(G)) denotes the chromatic (clique) number of G. It is known ...that for every 2K2-free graph G, χ(G)≤ω(G)+12, and the class of (2K2,3K1)-free graphs does not admit a linear χ-binding function. In this paper, we are interested in classes of 2K2-free graphs that admit a linear χ-binding function. We show that the class of (2K2,H)-free graphs, where H∈{K1+P4,K1+C4,P2∪P3¯,HVN,K5−e,K5} admits a linear χ-binding function. Also, we show that some superclasses of 2K2-free graphs are χ-bounded.
PDF
