共查询到20条相似文献,搜索用时 15 毫秒
1.
Wolfgang Mader 《Combinatorica》2005,25(4):425-438
We determine all graphs on n ≥ 3 vertices with 3n-6 edges which do not contain a subdivision of K5. These are exactly the graphs which one gets from any number of disjoint maximal planar graphs by successively pasting along
triangles. 相似文献
2.
We show that a graph of girth greater than 6 log k+3 and minimum degree at least 3 has a minor of minimum degree greater than k. This is best possible up to a factor of at most 9/4. As a corollary, every graph of girth at least 6 log r+3 log log r+c and minimum degree at least 3 has a K
r
minor. 相似文献
3.
《Quaestiones Mathematicae》2013,36(2):259-264
AbstractAn F-free colouring of a graph G is a partition {V1,V2,…,Vn} of the vertex set V(G) of G such that F is not an induced subgraph of G[Vi] for each i. A graph is uniquely F-free colourable if any two .F-free colourings induce the same partition of V(G). We give a constructive proof that uniquely C4-free colourable graphs exist. 相似文献
4.
A.V. Kostochka 《Journal of Graph Theory》2014,75(4):377-386
Let denote the graph obtained from the complete graph by deleting the edges of some ‐subgraph. The author proved earlier that for each fixed s and , every graph with chromatic number has a minor. This confirmed a partial case of the corresponding conjecture by Woodall and Seymour. In this paper, we show that the statement holds already for much smaller t, namely, for . 相似文献
5.
Gregory M. Constantine 《Annals of Combinatorics》2005,9(2):163-167
Can a complete graph on an even number n (> 4) of vertices be properly edge-colored with n − 1 colors in such a way that the edges can be partitioned into edge-disjoint colorful isomorphic spanning trees? A spanning treee is colorful if all n − 1 colors occur among its edges. It is proved that this is possible to accomplish whenever n is a power of two.Received July 24, 2001 相似文献
6.
Circular Chromatic Number and
Mycielski Graphs 总被引:7,自引:0,他引:7
As a natural generalization of graph coloring, Vince
introduced the star chromatic number of a graph
G and denoted it by
*(G). Later, Zhu called it circular
chromatic number and denoted it by c(G). Let (G)
be the chromatic number of G.
In this paper, it is shown that if the complement of
G is non-hamiltonian, then
c(G)=(G). Denote by M(G)
the Mycielski graph of G.
Recursively define Mm(G)=M(Mm–1(G)). It was conjectured that if
mn–2, then c(Mm(Kn))=(Mm(Kn)). Suppose that
G is a graph on n vertices.
We prove that if
, then
c(M(G))=(M(G)). Let S be the set of vertices of degree
n–1 in
G. It is proved that if
|S| 3, then
c(M(G))=(M(G)), and if |S| 5, then c(M2(G))=(M2(G)), which implies the known results of
Chang, Huang, and Zhu that if n3, c(M(Kn))=(M(Kn)), and if
n5, then
c(M2(Kn))=(M2(Kn)).* Research supported by Grants from National Science
Foundation of China and Chinese Academy of
Sciences. 相似文献
7.
A sufficient condition for graphs with circular flow index less than 4 is found in this paper. In particular, we give a simple
proof of a result obtained by Galluccio and Goddyn (Combinatorica, 2002), and obtain a larger family of such graphs.
* Partially supported by the National Security Agency under Grants MDA904-01-1-0022. 相似文献
8.
We introduce and discuss generalizations of the problem of independent transversals. Given a graph property
, we investigate whether any graph of maximum degree at most d with a vertex partition into classes of size at least p admits a transversal having property
. In this paper we study this problem for the following properties
: “acyclic”, “H-free”, and “having connected components of order at most r”.
We strengthen a result of [13]. We prove that if the vertex set of a d-regular graph is partitioned into classes of size d+⌞d/r⌟, then it is possible to select a transversal inducing vertex disjoint trees on at most r vertices. Our approach applies appropriate triangulations of the simplex and Sperner’s Lemma. We also establish some limitations
on the power of this topological method.
We give constructions of vertex-partitioned graphs admitting no independent transversals that partially settles an old question
of Bollobás, Erdős and Szemerédi. An extension of this construction provides vertex-partitioned graphs with small degree such
that every transversal contains a fixed graph H as a subgraph.
Finally, we pose several open questions.
* Research supported by the joint Berlin/Zurichgrad uate program Combinatorics, Geometry, Computation, financed by the German
Science Foundation (DFG) and ETH Zürich.
† Research partially supported by Hungarian National Research Fund grants T-037846, T-046234 and AT-048826. 相似文献
9.
It is shown that the neighborhood complexes of a family of
vertex critical subgraphs of Kneser graphs—the stable Kneser
graphs introduced by L. Schrijver—are spheres up to homotopy.
Furthermore, it is shown that the neighborhood complexes of a
subclass of the stable Kneser graphs contain the boundaries of
associahedra (simplicial complexes encoding triangulations of a
polygon) as a strong deformation retract.* The first author was partially supported by the
Göran Gustafsson Foundation for Research in Natural
Sciences and Medicine. The second author was supported by the graduate
school Algorithmische Diskrete Mathematik, which is funded by
the Deutsche Forschungsgemeinschaft, grant GRK 219/3. The DAAD
partially supported a stay at KTH, Stockholm, in December 1998,
where this work was done: DAAD program AZ 313/S-PPP 相似文献
10.
We prove that each n-vertex plane graph with girth g≥4 admits a vertex coloring with at least ⌈n/2⌉+1 colors with no rainbow face, i.e., a face in which all vertices receive distinct colors. This proves a conjecture of
Ramamurthi and West. Moreover, we prove for plane graph with girth g≥5 that there is a vertex coloring with at least
if g is odd and
if g is even. The bounds are tight for all pairs of n and g with g≥4 and n≥5g/2−3.
* Supported in part by the Ministry of Science and Technology of Slovenia, Research Project Z1-3129 and by a postdoctoral
fellowship of PIMS.
** Institute for Theoretical Computer Science is supported by Ministry of Education of CzechR epublic as project LN00A056. 相似文献
11.
We explore properties of edge colorings of graphs dened
by set intersections. An edge coloring of a graph
G with vertex set
V ={1,2, . . . ,
n} is called
transitive if one can
associate sets F
1,F
2, . .
.,F
n
to vertices of G so that for
any two edges ij,kl E(G), the color of
ij and
kl is the same if and only if
F
i
F
j
= F
k
F
l
. The term
transitive refers to a
natural partial order on the color set of these
colorings.We prove a canonical Ramsey type result for transitive
colorings of complete graphs which is equivalent to a stronger
form of a conjecture of A. Sali on hypergraphs. This—through the
reduction of Sali—shows that the dimension of
n-element lattices is
o(n) as conjectured by Füredi and
Kahn.The proof relies on concepts and results which seem to
have independent interest. One of them is a generalization of
the induced matching lemma of Ruzsa and Szemerédi for transitive
colorings. * Research supported in part by OTKA Grant
T029074. 相似文献
12.
A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, such that no two adjacent or incident elements receive the same color. A graph G is s-degenerate for a positive integer s if G can be reduced to a trivial graph by successive removal of vertices with degree ≤s. We prove that an s-degenerate graph G has a total coloring with Δ+1 colors if the maximum degree Δ of G is sufficiently large, say Δ≥4s+3. Our proof yields an efficient algorithm to find such a total coloring. We also give a lineartime algorithm to find a total
coloring of a graph G with the minimum number of colors if G is a partial k-tree, that is, the tree-width of G is bounded by a fixed integer k. 相似文献
13.
It is shown that every 5-connected graph embedded in the
projective plane with face-width at least 3 contains the
complete graph on 6 vertices as a minor.* Supported in part by the Ministry of Science and
Technology of Slovenia, Research Project
J1-0502-0101-98. 相似文献
14.
In this paper we show that, if G is a Berge graph such that neither G nor its complement
contains certain induced subgraphs, named proper wheels and long prisms, then either G is a basic perfect graph( a bipartite graph, a line graph of a bipartite graph or the complement of such graphs) or it has
a skew partition that cannot occur in a minimally imperfect graph. This structural result implies that G is perfect.
This work was supported in part by NSF grant DMI-0352885 and ONR grant N00014-03-1-0188. 相似文献
15.
We prove that, for each xed real number
c > 1/3, the triangle-free
graphs of minimum degree at least cn (where n is the number of vertices) have
bounded chromatic number. This problem was raised by Erds and
Simonovits in 1973 who pointed out that there is no such result
for c < 1/3. 相似文献
16.
Carsten Thomassen 《Combinatorica》2007,27(2):241-243
We prove that, for each fixed real number c > 0, the pentagon-free graphs of minimum degree at least cn (where n is the number of vertices) have bounded chromatic number. This problem was raised by Erdős and Simonovits in 1973. A similar
result holds for any other fixed odd cycle, except the triangle for which there is no such result for c<1/3. 相似文献
17.
In this paper we introduce two tree-width-like graph
invariants. The first graph invariant, which we denote by
=(G), is defined in terms of positive
semi-definite matrices and is similar to the graph invariant
(G), introduced by Colin de Verdière in
[J. Comb. Theory, Ser. B., 74:121–146, 1998]. The second graph
invariant, which we denote by (G), is defined in terms of a certain
connected subgraph property and is similar to (G), introduced by van der Holst,
Laurent, and Schrijver in [J. Comb. Theory, Ser. B., 65:291–304,
1995]. We give some theorems on the behaviour of these
invariants under certain transformations. We show that
=(G)=(G)
for any graph G with
=(G)4, and we give minimal forbidden
minor characterizations for the graphs satisfying
=(G)k
for k=1,2,3,4.This paper is extracted from two chapters of [7].
This work was done while the author was at the Centrum voor
Wiskunde en Informatica, Kruislaan 413, 1098 SJ Amsterdam, The
Netherlands. 相似文献
18.
Fan Chung 《Annals of Combinatorics》2005,9(1):1-19
We consider Laplacians for directed graphs and examine their eigenvalues. We introduce a notion of a circulation in a directed graph and its connection with the Rayleigh quotient. We then define a Cheeger constant and establish the Cheeger inequality for directed graphs. These relations can be used to deal with various problems that often arise in the study of non-reversible Markov chains including bounding the rate of convergence and deriving comparison theorems.Received September 8, 2004 相似文献
19.
By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. It is known that connected graphs G that maximize the signless Laplacian spectral radius ρ(Q(G)) over all connected graphs with given numbers of vertices and edges are (degree) maximal. For a maximal graph G with n vertices and r distinct vertex degrees δr>δr-1>?>δ1, it is proved that ρ(Q(G))<ρ(Q(H)) for some maximal graph H with n+1 (respectively, n) vertices and the same number of edges as G if either G has precisely two dominating vertices or there exists an integer such that δi+δr+1-i?n+1 (respectively, δi+δr+1-i?δl+δr-l+1). Graphs that maximize ρ(Q(G)) over the class of graphs with m edges and m-k vertices, for k=0,1,2,3, are completely determined. 相似文献
20.
Received: October 10, 1996 相似文献