Coloring the edges of a random graph without a monochromatic giant component.
Spöhel, Reto, Steger, Angelika, Thomas, Henning (2010)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Spöhel, Reto, Steger, Angelika, Thomas, Henning (2010)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Achlioptas, Dimitris, Molloy, Michael (1999)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Katarzyna Rybarczyk (2017)
Discussiones Mathematicae Graph Theory
Similarity:
We study problems related to the chromatic number of a random intersection graph G (n,m, p). We introduce two new algorithms which colour G (n,m, p) with almost optimum number of colours with probability tending to 1 as n → ∞. Moreover we find a range of parameters for which the chromatic number of G (n,m, p) asymptotically equals its clique number.
E.J. Cockayne, C.M. Mynhardt (1999)
Discussiones Mathematicae Graph Theory
Similarity:
A set X of vertices of a graph G is said to be 1-dependent if the subgraph of G induced by X has maximum degree one. The 1-dependent Ramsey number t₁(l,m) is the smallest integer n such that for any 2-edge colouring (R,B) of Kₙ, the spanning subgraph B of Kₙ has a 1-dependent set of size l or the subgraph R has a 1-dependent set of size m. The 2-edge colouring (R,B) is a t₁(l,m) Ramsey colouring of Kₙ if B (R, respectively) does not contain a 1-dependent set of size l (m, respectively);...
Beer, Elizabeth, Fill, James Allen, Janson, Svante, Scheinerman, Edward R. (2011)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Krivelevich, Michael (2002)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Bolobás, Béla, Riordan, Oliver (2000)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Oleg V. Borodin, Anna O. Ivanova (2013)
Discussiones Mathematicae Graph Theory
Similarity:
We prove that every planar graph with maximum degree ∆ is strong edge (2∆−1)-colorable if its girth is at least 40 [...] +1. The bound 2∆−1 is reached at any graph that has two adjacent vertices of degree ∆.
William F. Klostermeyer, Gary MacGillivray (2004)
Discussiones Mathematicae Graph Theory
Similarity:
We examine subgraphs of oriented graphs in the context of oriented coloring that are analogous to cliques in traditional vertex coloring. Bounds on the sizes of these subgraphs are given for planar, outerplanar, and series-parallel graphs. In particular, the main result of the paper is that a planar graph cannot contain an induced subgraph D with more than 36 vertices such that each pair of vertices in D are joined by a directed path of length at most two.
Král', Daniel, West, Douglas B. (2009)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Prakash, Anupam, Spöhel, Reto, Thomas, Henning (2009)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Robert Fidytek, Hanna Furmańczyk, Paweł Żyliński (2009)
Discussiones Mathematicae Graph Theory
Similarity:
The Kneser graph K(n,k) is the graph whose vertices correspond to k-element subsets of set {1,2,...,n} and two vertices are adjacent if and only if they represent disjoint subsets. In this paper we study the problem of equitable coloring of Kneser graphs, namely, we establish the equitable chromatic number for graphs K(n,2) and K(n,3). In addition, for sufficiently large n, a tight upper bound on equitable chromatic number of graph K(n,k) is given. Finally, the cases of K(2k,k) and K(2k+1,k)...
Ove Frank (1988)
Mathématiques et Sciences Humaines
Similarity:
Arnfried Kemnitz, Massimiliano Marangio, Margit Voigt (2016)
Discussiones Mathematicae Graph Theory
Similarity:
Let G = (V,E) be a simple graph and for every edge e ∈ E let L(e) be a set (list) of available colors. The graph G is called L-edge colorable if there is a proper edge coloring c of G with c(e) ∈ L(e) for all e ∈ E. A function f : E → ℕ is called an edge choice function of G and G is said to be f-edge choosable if G is L-edge colorable for every list assignment L with |L(e)| = f(e) for all e ∈ E. Set size(f) = ∑e∈E f(e) and define the sum choice index χ′sc(G) as the minimum of size(f)...
Frieze, Alan, Mubayi, Dhruv (2008)
The Electronic Journal of Combinatorics [electronic only]
Similarity: