TITLE

ON RAMSEY (K1,2,Kn)-MINIMAL GRAPHS

AUTHOR(S)
HAŁUSZCZAK, MARIUSZ
PUB. DATE
May 2012
SOURCE
Discussiones Mathematicae: Graph Theory;2012, Vol. 32 Issue 2, p331
SOURCE TYPE
DOC. TYPE
Article
ABSTRACT
Let F be a graph and let G, H denote nonempty families of graphs. We write F â†’ (G,H) if in any 2-coloring of edges of F with red and blue, there is a red subgraph isomorphic to some graph from G or a blue subgraph isomorphic to some graph from H. The graph F without isolated vertices is said to be a (G,H)-minimal graph if F â†’ (G,H) and F - e â†› (G,H) for every e Îµ E(F). We present a technique which allows to generate infinite family of (G,H)- minimal graphs if we know some special graphs. In particular, we show how to receive infinite family of (K1,2,Kn)-minimal graphs, for every n = 3.
ACCESSION #
86440297

Related Articles

• On Three-Color Ramsey Number of Paths. Maherani, L.; Omidi, G.; Raeisi, G.; Shahsiah, M. // Graphs & Combinatorics;Nov2015, Vol. 31 Issue 6, p2299

For given graphs \$\$G_1, G_2, \ldots , G_t\$\$ , the multicolor Ramsey number \$\$R(G_1, G_2, \ldots , G_t)\$\$ is the smallest positive integer \$\$n\$\$ , such that if the edges of the complete graph \$\$K_n\$\$ are partitioned into \$\$t\$\$ disjoint color classes giving \$\$t\$\$ graphs \$\$H_1,H_2,\ldots ,H_t\$\$ ,...

• ON RAMSEY (K1,2, Kn)-MINIMAL GRAPHS. Haluszczak, Mariusz // Discussiones Mathematicae: Graph Theory;2012, Vol. 32 Issue 3, p331

Let F be a graph and let G, H denote nonempty families of graphs. We write F â†’ (G, H) if in any 2-coloring of edges of F with red and blue, there is a red subgraph isomorphic to some graph from G or a blue subgraph isomorphic to some graph from H. The graph F without isolated vertices is...

• Ideal Graph of a Graph. Manoharan, R.; Vasuki, R.; Manisekaran, R. // International Journal of Mathematical Combinatorics;Sep2011, Vol. 3, p11

In this paper, we introduce ideal graph of a graph and study some of its properties. We characterize connectedness, isomorphism of graphs and coloring property of a graph using ideal graph. Also, we give an upper bound for chromatic number of a graph.

• ON THE RAINBOW CONNECTION OF CARTESIAN PRODUCTS AND THEIR SUBGRAPHS. KLAVžAR, SANDI; MEKIš, GAšPER // Discussiones Mathematicae: Graph Theory;2012, Vol. 32 Issue 4, p783

Rainbow connection number of Cartesian products and their subgraphs are considered. Previously known bounds are compared and non-existence of such bounds for subgraphs of products are discussed. It is shown that the rainbow connection number of an isometric subgraph of a hypercube is bounded...

• FROM RECONSTRUCTION CONJECTURE TOWARDS A LEMMA. Banerjee, Subhashis; Sensarma, Debajit; Basuli, Krishnendu; Naskar, Saptarshi; Sarma, Samar Sen // Computer Science & Engineering;Feb2012, Vol. 2 Issue 1, p53

The Reconstruction Conjecture has been synthesized under the characterized of matching Polynomial. A Polynomial time algorithm for generating matching polynomial of an undirected graph is given. Algorithms are given for reconstructing a graph from its node-deleted and edge-deleted subgraphs....

• Characterization and Construction of Permutation Graphs. Gervacio, Severino V.; Rapanut, Teofina A.; Ramos, Phoebe Chloe F. // Open Journal of Discrete Mathematics;Jan2013, Vol. 3 Issue 1, p33

If Ïƒ is a permutation of {1, 2,---,n} , the graph GÏƒ has vertices 1, 2,---,n where xy is an edge of GÏƒ if and only if ( x, y) or ( y, x) is an inversion of Ïƒ . Any graph isomorphic to GÏƒ is called a permutation graph. In 1967 Gallai characterized permutation graphs in terms of...

• Highly Hamiltonian K1,3P4-Free Graphs. Ramos, R. E.; Babierra, A. L. // Southeast Asian Bulletin of Mathematics;2012, Vol. 36 Issue 4, p529

A graph G is K1,3P4-free if G contains no induced subgraph isomorphic to K1,3 nor P4. We characterize here the fully cycle extendable 2-connected K1,3P4-free graphs, the panconnected 3-connected K1,3P4-free graphs, the path extendable 3-connected K1,3P4-free graphs, and the q-edge hamiltonian...

• Universal H-Colourable Graphs. Broere, Izak; Heidema, Johannes // Graphs & Combinatorics;Sep2013, Vol. 29 Issue 5, p1193

Rado constructed a (simple) denumerable graph R with the positive integers as vertex set with the following edges: for given m and n with m < n, m is adjacent to n if n has a 1 in the mth position of its binary expansion. It is well known that R is a universal graph in the set...

• Small Edge Sets Meeting all Triangles of a Graph. Aparna Lakshmanan, S.; Bujtás, Cs.; Tuza, Zs. // Graphs & Combinatorics;May2012, Vol. 28 Issue 3, p381

It was conjectured in 1981 by the third author that if a graph G does not contain more than t pairwise edge-disjoint triangles, then there exists a set of at most 2 t edges that shares an edge with each triangle of G. In this paper, we prove this conjecture for odd-wheel-free graphs and for...

Share