共查询到20条相似文献，搜索用时 28 毫秒
1.
《Journal of Graph Theory》2018,89(3):288-303
A gem is a graph that consists of a path on four vertices plus a vertex adjacent to all four vertices of the path. A co‐gem is the complement of a gem. We prove that every (gem, co‐gem)‐free graph G satisfies the inequality (a special case of a conjecture of Gyárfás) and the inequality (a special case of a conjecture of Reed). Moreover, we give an ‐time algorithm that computes the chromatic number of any (gem, co‐gem)‐free graph with n vertices, while the existing algorithm in the literature takes . 相似文献
2.
Given a graph G of order n, the σ‐polynomial of G is the generating function where is the number of partitions of the vertex set of G into i nonempty independent sets. Such polynomials arise in a natural way from chromatic polynomials. Brenti (Trans Am Math Soc 332 (1992), 729–756) proved that σ‐polynomials of graphs with chromatic number at least had all real roots, and conjectured the same held for chromatic number . We affirm this conjecture. 相似文献
3.
Colin McDiarmid Dieter Mitsche Pawe&#x; Pra&#x;at 《Random Structures and Algorithms》2019,54(4):589-614
A clique coloring of a graph is a coloring of the vertices so that no maximal clique is monochromatic (ignoring isolated vertices). The smallest number of colors in such a coloring is the clique chromatic number. In this paper, we study the asymptotic behavior of the clique chromatic number of the random graph ??(n,p) for a wide range of edge‐probabilities p = p(n). We see that the typical clique chromatic number, as a function of the average degree, forms an intriguing step function. 相似文献
4.
In a search for triangle-free graphs with arbitrarily large chromatic numbers, Mycielski developed a graph transformation that transforms a graph G into a new graph μ(G), we now call the Mycielskian of G, which has the same clique number as G and whose chromatic number equals χ(G) + 1. Chang, Huang, and Zhu [G. J. Chang, L. Huang, & X. Zhu, Discrete Math, to appear] have investigated circular chromatic numbers of Mycielskians for several classes of graphs. In this article, we study circular chromatic numbers of Mycielskians for another class of graphs G. The main result is that χc(μ(G)) = χ(μ(G)), which settles a problem raised in [G. J. Chang, L. Huang, & X. Zhu, Discrete Math, to appear, and X. Zhu, to appear]. As χc(G) = and χ(G) = , consequently, there exist graphs G such that χc(G) is as close to χ(G) − 1 as you want, but χc(μ(G)) = χ(μ(G)). © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 63–71, 1999 相似文献
5.
一个图的Wiener指数是指这个图中所有点对的距离和.Wiener指数在理论化学中有广泛应用. 本文刻画了给定顶点数及特定参数如色数或团数的图中Wiener指数达最小值的图, 同时也刻画了给定顶点数及团数的图中Wiener指数达最大值的图. 相似文献
6.
Ioan Tomescu 《Journal of Graph Theory》2003,43(3):210-222
In the set of graphs of order n and chromatic number k the following partial order relation is defined. One says that a graph G is less than a graph H if ci(G) ≤ ci(H) holds for every i, k ≤ i ≤ n and at least one inequality is strict, where ci(G) denotes the number of i‐color partitions of G. In this paper the first ? n/2 ? levels of the diagram of the partially ordered set of connected 3‐chromatic graphs of order n are described. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 210–222, 2003 相似文献
7.
Irena Penev 《Journal of Graph Theory》2017,84(1):57-92
A class of graphs is hereditary if it is closed under isomorphism and induced subgraphs. A class of graphs is χ‐bounded if there exists a function such that for all graphs , and all induced subgraphs H of G, we have that . We prove that proper homogeneous sets, clique‐cutsets, and amalgams together preserve χ‐boundedness. More precisely, we show that if and are hereditary classes of graphs such that is χ‐bounded, and such that every graph in either belongs to or admits a proper homogeneous set, a clique‐cutset, or an amalgam, then the class is χ‐bounded. This generalizes a result of [J Combin Theory Ser B 103(5) (2013), 567–586], which states that proper homogeneous sets and clique‐cutsets together preserve χ‐boundedness, as well as a result of [European J Combin 33(4) (2012), 679–683], which states that 1‐joins preserve χ‐boundedness. The house is the complement of the four‐edge path. As an application of our result and of the decomposition theorem for “cap‐free” graphs from [J Graph Theory 30(4) (1999), 289–308], we obtain that if G is a graph that does not contain any subdivision of the house as an induced subgraph, then . 相似文献
8.
Hong Lin Xiao-feng Guo 《应用数学学报(英文版)》2007,23(1):155-160
Let φ(G),κ(G),α(G),χ(G),cl(G),diam(G)denote the number of perfect matchings,connectivity,independence number,chromatic number,clique number and diameter of a graph G,respectively.In this note,by constructing some extremal graphs,the following extremal problems are solved:1.max{φ(G):|V(G)|=2n,κ(G)≤k}=k[(2n-3)!!],2.max{φ(G):|V(G)|=2n,α(G)≥k}=[multiply from i=0 to k-1(2n-k-i)[(2n-2k-1)!!],3.max{φ(G):|V(G)|=2n,χ(G)≤k}=φ(T_(k,2n))T_(k,2n)is the Turán graph,that is a complete k-partite graphon 2n vertices in which all parts are as equal in size as possible,4.max{φ(G):|V(G)|=2n,cl(G)=2}=n1,5.max{φ(G):|V(G)|=2n,diam(G)≥2}=(2n-2)(2n-3)[(2n-5)!!],max{φ(G):|V(G)|=2n,diam(G)≥3}=(n-1)~2[(2n-5)!!]. 相似文献
9.
对于每一个含有最小元素0的偏序集（P,≤）可以得到一个与其关联的图G（P）.本文主要通过代数的方法研究了所得关联图G（P）的性质,证明了如果G（P）的色数和团数是有限的,那么色数和团数都仅比P的极小素理想的个数大1. 相似文献
10.
《Journal of Graph Theory》2018,88(2):312-336
A long unichord in a graph is an edge that is the unique chord of some cycle of length at least 5. A graph is long unichord free if it does not contain any long unichord. We prove a structure theorem for long unichord free graph. We give an time algorithm to recognize them. We show that any long unichord free graph G can be colored with at most colors, where ω is the maximum number of pairwise adjacent vertices in G. 相似文献
11.
Xuding Zhu 《Journal of Graph Theory》2005,48(3):186-209
For 1 ≤ d ≤ k, let Kk/d be the graph with vertices 0, 1, …, k ? 1, in which i ～j if d ≤ |i ? j| ≤ k ? d. The circular chromatic number χc(G) of a graph G is the minimum of those k/d for which G admits a homomorphism to Kk/d. The circular clique number ωc(G) of G is the maximum of those k/d for which Kk/d admits a homomorphism to G. A graph G is circular perfect if for every induced subgraph H of G, we have χc(H) = ωc(H). In this paper, we prove that if G is circular perfect then for every vertex x of G, NG[x] is a perfect graph. Conversely, we prove that if for every vertex x of G, NG[x] is a perfect graph and G ? N[x] is a bipartite graph with no induced P5 (the path with five vertices), then G is a circular perfect graph. In a companion paper, we apply the main result of this paper to prove an analog of Haj?os theorem for circular chromatic number for k/d ≥ 3. Namely, we shall design a few graph operations and prove that for any k/d ≥ 3, starting from the graph Kk/d, one can construct all graphs of circular chromatic number at least k/d by repeatedly applying these graph operations. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 186–209, 2005 相似文献
12.
The tensor product of graphs , and is defined by and Let be the fractional chromatic number of a graph . In this paper, we prove that if one of the three graphs , and is a circular clique, 相似文献
13.
We introduce properties of Boolean algebras which are closely related to the existence of winning strategies in the Banach‐Mazur Boolean game. A σ‐short Boolean algebra is a Boolean algebra that has a dense subset in which every strictly descending sequence of length ω does not have a nonzero lower bound. We give a characterization of σ‐short Boolean algebras and study properties of σ‐short Boolean algebras. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
14.
Maria Chudnovsky T. Karthick Peter Maceli Frédéric Maffray 《Journal of Graph Theory》2020,95(4):527-542
15.
In this paper, a new class of rings, called FIC rings, is introduced for studying quasi-zero-divisor graphs of rings. Let R be a ring. The quasi-zero-divisor graph of R, denoted by Γ_*(R), is a directed graph defined on its nonzero quasi-zero-divisors, where there is an arc from a vertex x to another vertex y if and only if x Ry = 0. We show that the following three conditions on an FIC ring R are equivalent:(1) χ(R) is finite;(2) ω(R) is finite;(3)Nil_*R is finite where Nil_*R equals the finite intersection of prime ideals. Furthermore, we also completely determine the connectedness, the diameter and the girth of Γ_*(R). 相似文献
16.
We prove several dichotomy theorems which extend some known results on σ‐bounded and σ‐compact pointsets. In particular we show that, given a finite number of $Delta ^{1}_{1}$ equivalence relations $mathrel {mathsf {F}}_1,dots ,mathrel {mathsf {F}}_n$, any $Sigma ^{1}_{1}$ set A of the Baire space either is covered by compact $Delta ^{1}_{1}$ sets and lightface $Delta ^{1}_{1}$ equivalence classes of the relations $mathrel {mathsf {F}}_i$, or A contains a superperfect subset which is pairwise $mathrel {mathsf {F}}_i$‐inequivalent for all i = 1, …, n. Further generalizations to $Sigma ^{1}_{2}$ sets A are obtained. 相似文献
17.
We derive decomposition theorems for P6, K1 + P4‐free graphs, P5, K1 + P4‐free graphs and P5, K1 + C4‐free graphs, and deduce linear χ‐binding functions for these classes of graphs (here, Pn (Cn) denotes the path (cycle) on n vertices and K1 + G denotes the graph obtained from G by adding a new vertex and joining it with every vertex of G). Using the same techniques, we also obtain an optimal χ‐binding function for P5, C4‐free graphs which is an improvement over that given in [J. L. Fouquet, V. Giakoumakis, F. Maire, and H. Thuillier, 11 , Discrete Math, 146, 33–44.]. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 293–306, 2007 相似文献
18.
We show a connection between two concepts that have hitherto been investigated separately, namely convex‐round graphs and circular cliques. The connections are twofold. We prove that the circular cliques are precisely the cores of convex‐round graphs; this implies that convex‐round graphs are circular‐perfect, a concept introduced recently by Zhu [10]. Secondly, we characterize maximal Kr‐free convex‐round graphs and show that they can be obtained from certain circular cliques in a simple fashion. Our proofs rely on several structural properties of convex‐round graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 182–194, 2002 相似文献
19.
Stanley Burris 《Mathematical Logic Quarterly》1994,40(1):141-142
We present two conditions which are equivalent to having an almost χ0-categorical model companion. Mathematics Subject Classification: 03C35. 相似文献
20.
Circular chromatic number, χc is a natural generalization of chromatic number. It is known that it is NP ‐hard to determine whether or not an arbitrary graph G satisfies χ(G)=χc(G). In this paper we prove that this problem is NP ‐hard even if the chromatic number of the graph is known. This answers a question of Xuding Zhu. Also we prove that for all positive integers k ≥ 2 and n ≥ 3, for a given graph G with χ(G) = n, it is NP ‐complete to verify if . © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 226–230, 2004 相似文献
