共查询到20条相似文献,搜索用时 15 毫秒
1.
Star chromatic numbers of graphs 总被引:10,自引:0,他引:10
We investigate the relation between the star-chromatic number (G) and the chromatic number (G) of a graphG. First we give a sufficient condition for graphs under which their starchromatic numbers are equal to their ordinary chromatic numbers. As a corollary we show that for any two positive integersk, g, there exists ak-chromatic graph of girth at leastg whose star-chromatic number is alsok. The special case of this corollary withg=4 answers a question of Abbott and Zhou. We also present an infinite family of triangle-free planar graphs whose star-chromatic number equals their chromatic number. We then study the star-chromatic number of An infinite family of graphs is constructed to show that for each >0 and eachm2 there is anm-connected (m+1)-critical graph with star chromatic number at mostm+. This answers another question asked by Abbott and Zhou. 相似文献
2.
We prove that for every constant >0 the chromatic number of the random graphG(n, p) withp=n
–1/2– is asymptotically almost surely concentrated in two consecutive values. This implies that for any <1/2 and any integer valued functionr(n)O(n
) there exists a functionp(n) such that the chromatic number ofG(n,p(n)) is preciselyr(n) asymptotically almost surely.Research supported in part by a USA Israeli BSF grant and by a grant from the Israel Science Foundation.Research supported in part by a Charles Clore Fellowship. 相似文献
3.
The concept of the star chromatic number of a graph was introduced by Vince (A. Vince, Star chromatic number, J. Graph Theory 12 (1988), 551–559), which is a natural generalization of the chromatic number of a graph. This paper calculates the star chromatic numbers of three infinite families of planar graphs. More precisely, the first family of planar graphs has star chromatic numbers consisting of two alternating infinite decreasing sequences between 3 and 4; the second family of planar graphs has star chromatic numbers forming an infinite decreasing sequence between 3 and 4; and the third family of planar graphs has star chromatic number 7/2. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 33–42, 1998 相似文献
4.
C. Thomassen 《Combinatorica》1983,3(1):133-134
We answer a question of Erdős [1], [2] by showing that any graph of uncountable chromatic number contains an edge through
which there are cycles of all (but finitely many) lengths. 相似文献
5.
Vojtěch Rödl 《Combinatorica》1982,2(4):377-383
P. Erdős and A. Hajnal asked the following question. Does there exist a constant ε>0 with the following property: If every
subgraphH of a graphG can be made bipartite by the omission of at most ε|H| edges where |H| denotes the number of vertices ofH thenx(H) ≦ 3.
The aim of this note is to give a negative answer to this question and consider the analogous problem for hypergraphs. The
first was done also by L. Lovász who used a different construction. 相似文献
6.
In 1973, P. Erdös conjectured that for eachkε2, there exists a constantc k so that ifG is a graph onn vertices andG has no odd cycle with length less thanc k n 1/k , then the chromatic number ofG is at mostk+1. Constructions due to Lovász and Schriver show thatc k , if it exists, must be at least 1. In this paper we settle Erdös’ conjecture in the affirmative. We actually prove a stronger result which provides an upper bound on the chromatic number of a graph in which we have a bound on the chromatic number of subgraphs with small diameter. 相似文献
7.
Several constructions of 4-critical planar graphs are given. These provide answers to two questions of B. Grünbaum and give improved bounds for the maximum edge density of such graphs. 相似文献
8.
Igor Kříž 《Combinatorica》1989,9(2):227-229
We present a purely graph-theoretical construction of highly chromatic graphs without short cycles. 相似文献
9.
For any graphG and numbern≧1 two functionsf, g fromV(G) into {1, 2, ...,n} are adjacent if for all edges (a, b) ofG, f(a) ≠g(b). The graph of all such functions is the colouring graph ℒ(G) ofG. We establish first that χ(G)=n+1 implies χ(ℒ(G))=n iff χ(G ×H)=n+1 for all graphsH with χ(H)≧n+1. Then we will prove that indeed for all 4-chromatic graphsG χ(ℒ(G))=3 which establishes Hedetniemi’s [3] conjecture for 4-chromatic graphs.
This research was supported by NSERC grant A7213 相似文献
10.
A crucial step in the Erdös-Rényi (1960) proof that the double-jump threshold is also the planarity threshold for random graphs is shown to be invalid. We prove that whenp=1/n, almost all graphs do not contain a cycle with a diagonal edge, contradicting Theorem 8a of Erdös and Rényi (1960). As a consequence, it is proved that the chromatic number is 3 for almost all graphs whenp=1/n.Research supported U.S. National Science Foundation Grants DMS-8303238 and DMS-8403646. The research was conducted on an exchange visit by Professor Wierman to Poland supported by the national Academy of Sciences of the USA and the Polish Academy of Sciences. 相似文献
11.
W. -L. Hsu 《Combinatorica》1986,6(4):381-385
This paper describes a decomposition scheme for coloring perfect graphs. Based on this scheme, one need only concentrate on
coloring highly connected (at least 3-connected) perfect graphs. This idea is illustrated on planar perfect graphs, which
yields a straightforward coloring algorithm. We suspect that, under appropriate definition, highly connected perfect graphs
might possess certain regular properties that are amenable to coloring algorithms.
This research has been supported in part by National Science Foundation under grant ECS—8105989 to Northwestern University. 相似文献
12.
Let d(σ) stand for the defining number of the colouring σ. In this paper we consider and for the onto χ-colourings γ of the circular complete graph Kn,d. In this regard we obtain a lower bound for dmin(Kn,d) and we also prove that this parameter is asymptotically equal to χ-1. Also, we show that when χ?4 and s≠0 then dmax(Kχd-s,d)=χ+2s-3, and, moreover, we prove an inequality relating this parameter to the circular chromatic number for any graph G. 相似文献
13.
René Peeters 《Combinatorica》1996,16(3):417-431
We study the relationship between the minimum dimension of an orthogonal representation of a graph over a finite field and the chromatic number of its complement. It turns out that for some classes of matrices defined by a graph the 3-colorability problem is equivalent to deciding whether the class defined by the graph contains a matrix of rank 3 or not. This implies the NP-hardness of determining the minimum rank of a matrix in such a class. Finally we give for any class of matrices defined by a graph that is interesting in this respect a reduction of the 3-colorability problem to the problem of deciding whether or not this class contains a matrix of rank equal to three.The author is financially supported by the Cooperation Centre Tilburg and Eindhoven Universities. 相似文献
14.
L. A. Székely 《Combinatorica》1984,4(2-3):213-218
LetH be a set of positive real numbers. We define the geometric graphG
H
as follows: the vertex set isR
n
(or the unit circleS
1) andx, y are joined if their distance belongs toH. We define the measurable chromatic number of geometric graphs as the minimum number of classes in a measurable partition
into independent sets.
In this paper we investigate the difference between the notions of the ordinary and measurable chromatic numbers. We also
prove upper and lower bounds on the Lebesgue upper density of independent sets. 相似文献
15.
This article investigates the generators of certain homogeneous ideals which are associated with graphs with bounded independence
numbers. These ideals first appeared in the theory oft-designs. The main theorem suggests a new approach to the Clique Problem which isNP-complete. This theorem has a more general form in commutative algebra dealing with ideals associated with unions of linear
varieties. This general theorem is stated in the article; a corollary to it generalizes Turán’s theorem on the maximum graphs
with a prescribed clique number.
Research supported in part by NSF Grant MCS77-03533. 相似文献
16.
An r-edge-coloring of a graph G is a surjective assignment of r colors to the edges of G. A heterochromatic tree is an edge-colored tree in which any two edges have different colors. The heterochromatic tree partition number of an r-edge-colored graph G, denoted by tr(G), is the minimum positive integer p such that whenever the edges of the graph G are colored with r colors, the vertices of G can be covered by at most p vertex-disjoint heterochromatic trees. In this paper we give an explicit formula for the heterochromatic tree partition number of an r-edge-colored complete bipartite graph Km,n. 相似文献
17.
Jia Huang 《Discrete Mathematics》2007,307(15):1881-1897
The bondage number b(G) of a nonempty graph G is the cardinality of a smallest edge set whose removal from G results in a graph with domination number greater than the domination number γ(G) of G. Kang and Yuan proved b(G)?8 for every connected planar graph G. Fischermann, Rautenbach and Volkmann obtained some further results for connected planar graphs. In this paper, we generalize their results to connected graphs with small crossing numbers. 相似文献
18.
A graph G is said to be chromatic-choosable if ch(G)=χ(G). Ohba has conjectured that every graph G with 2χ(G)+1 or fewer vertices is chromatic-choosable. It is clear that Ohba's conjecture is true if and only if it is true for complete multipartite graphs. But for complete multipartite graphs, the graphs for which Ohba's conjecture has been verified are nothing more than K3*2,2*(k-3),1, K3,2*(k-1), and Ks+3,2*(k-s-1),1*s. These results have been obtained indirectly from the investigation about complete multipartite graphs by Gravier and Maffray and by Enomoto et al. In this paper we show that Ohba's conjecture is true for complete multipartite graphs K4,3,2*(k-4),1*2 and K5,3,2*(k-5),1*3. By the way, we give some discussions about a result of Enomoto et al. 相似文献
19.
Xiaoling Zhang 《Linear algebra and its applications》2008,428(7):1610-1619
In this paper, we study the largest Laplacian spectral radius of the bipartite graphs with n vertices and k cut edges and the bicyclic bipartite graphs, respectively. Identifying the center of a star K1,k and one vertex of degree n of Km,n, we denote by the resulting graph. We show that the graph (1?k?n-4) is the unique graph with the largest Laplacian spectral radius among the bipartite graphs with n vertices and k cut edges, and (n?7) is the unique graph with the largest Laplacian spectral radius among all the bicyclic bipartite graphs. 相似文献
20.
We prove that the size of the largest face of a 4-critical planar graph with 4 is at most one half the number of its vertices. Letf(n) denote the maximum of the sizes of largest faces of all such graphs withn vertices (n sufficiently large). We present an infinite family of graphs that shows
.All three authors gratefully acknowledge the support of the National Science and Engineering Research Council of Canada. 相似文献