Ramseyan properties of graphs.
DeLaVina, Ermelinda, Fajtlowicz, Siemion (1996)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
DeLaVina, Ermelinda, Fajtlowicz, Siemion (1996)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Hujter, M., Tuza, Zs. (1993)
Acta Mathematica Universitatis Comenianae. New Series
Similarity:
Tomáš Vetrík (2012)
Discussiones Mathematicae Graph Theory
Similarity:
The choice number of a graph G is the smallest integer k such that for every assignment of a list L(v) of k colors to each vertex v of G, there is a proper coloring of G that assigns to each vertex v a color from L(v). We present upper and lower bounds on the choice number of complete multipartite graphs with partite classes of equal sizes and complete r-partite graphs with r-1 partite classes of order two.
Brice Effantin, Hamamache Kheddouci (2007)
Discussiones Mathematicae Graph Theory
Similarity:
The Grundy number of a graph G is the maximum number k of colors used to color the vertices of G such that the coloring is proper and every vertex x colored with color i, 1 ≤ i ≤ k, is adjacent to (i-1) vertices colored with each color j, 1 ≤ j ≤ i -1. In this paper we give bounds for the Grundy number of some graphs and cartesian products of graphs. In particular, we determine an exact value of this parameter for n-dimensional meshes and some n-dimensional toroidal meshes. Finally,...
Csilla Bujtás, Zsolt Tuza (2016)
Discussiones Mathematicae Graph Theory
Similarity:
A K3-WORM coloring of a graph G is an assignment of colors to the vertices in such a way that the vertices of each K3-subgraph of G get precisely two colors. We study graphs G which admit at least one such coloring. We disprove a conjecture of Goddard et al. [Congr. Numer. 219 (2014) 161-173] by proving that for every integer k ≥ 3 there exists a K3-WORM-colorable graph in which the minimum number of colors is exactly k. There also exist K3-WORM colorable graphs which have a K3-WORM...
Krzysztof Turowski (2015)
Discussiones Mathematicae Graph Theory
Similarity:
For a graph G with a given subgraph H, the backbone coloring is defined as the mapping c : V (G) → N+ such that |c(u) − c(v)| ≥ 2 for each edge {u, v} ∈ E(H) and |c(u) − c(v)| ≥ 1 for each edge {u, v} ∈ E(G). The backbone chromatic number BBC(G,H) is the smallest integer k such that there exists a backbone coloring with maxv∈V (G) c(v) = k. In this paper, we present the algorithm for the backbone coloring of split graphs with matching backbone.
Brandt, Stephan, Brinkmann, Gunnar, Harmuth, Thomas (1998)
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 ∆.
Grytczuk, Jarosław (2007)
International Journal of Mathematics and Mathematical Sciences
Similarity:
Jan Kratochvíl (1995)
Commentationes Mathematicae Universitatis Carolinae
Similarity:
In this note, we introduce the notion of -Ramsey classes of graphs and we reveal connections to intersection dimensions of graphs.
John Mitchem, Patrick Morriss, Edward Schmeichel (1997)
Discussiones Mathematicae Graph Theory
Similarity:
We consider vertex colorings of graphs in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of the coloring is the sum of the costs incurred at each vertex. The cost chromatic number of a graph with respect to a cost set is the minimum number of colors necessary to produce a minimum cost coloring of the graph. We show that the cost chromatic number of maximal outerplanar and maximal planar graphs can be arbitrarily large and...