Nonrepetitive colorings of graphs -- a survey.
Grytczuk, Jarosław (2007)
International Journal of Mathematics and Mathematical Sciences
Similarity:
Grytczuk, Jarosław (2007)
International Journal of Mathematics and Mathematical Sciences
Similarity:
Hujter, M., Tuza, Zs. (1993)
Acta Mathematica Universitatis Comenianae. New Series
Similarity:
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.
Albertson, Michael O., Chappell, Glenn G., Kierstead, H.A., Kündgen, André, Ramamurthi, Radhika (2004)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Hajo Broersma, Bert Marchal, Daniel Paulusma, A.N.M. Salman (2009)
Discussiones Mathematicae Graph Theory
Similarity:
We continue the study on backbone colorings, a variation on classical vertex colorings that was introduced at WG2003. Given a graph G = (V,E) and a spanning subgraph H of G (the backbone of G), a λ-backbone coloring for G and H is a proper vertex coloring V→ {1,2,...} of G in which the colors assigned to adjacent vertices in H differ by at least λ. The algorithmic and combinatorial properties of backbone colorings have been studied for various types of backbones in a number of papers....
Jean-Sébastien Sereni, Zelealem B. Yilma (2013)
Discussiones Mathematicae Graph Theory
Similarity:
We provide a tight bound on the set chromatic number of a graph in terms of its chromatic number. Namely, for all graphs G, we show that χs(G) > ⌈log2 χ(G)⌉ + 1, where χs(G) and χ(G) are the set chromatic number and the chromatic number of G, respectively. This answers in the affirmative a conjecture of Gera, Okamoto, Rasmussen and Zhang.
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 ∆.
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,...
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.
Sebastian Urbański (1996)
Discussiones Mathematicae Graph Theory
Similarity:
The paper gives an account of previous and recent attempts to determine the order of a smallest graph not containing K₅ and such that every 2-coloring of its edges results in a monochromatic triangle. A new 14-vertex K₄-free graph with the same Ramsey property in the vertex coloring case is found. This yields a new construction of one of the only two known 15-vertex (3,3)-Ramsey graphs not containing K₅.
Alishahi, Meysam, Taherkhani, Ali, Thomassen, Carsten (2011)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Juvan, Martin, Mohar, Bojan, Thomas, Robin (1999)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Collins, Karen L., Trenk, Ann N. (2006)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Yuehua Bu, Ko-Wei Lih, Weifan Wang (2011)
Discussiones Mathematicae Graph Theory
Similarity:
An adjacent vertex distinguishing edge-coloring of a graph G is a proper edge-coloring o G such that any pair of adjacent vertices are incident to distinct sets of colors. The minimum number of colors required for an adjacent vertex distinguishing edge-coloring of G is denoted by χ'ₐ(G). We prove that χ'ₐ(G) is at most the maximum degree plus 2 if G is a planar graph without isolated edges whose girth is at least 6. This gives new evidence to a conjecture proposed in [Z. Zhang, L. Liu,...
Hosseini Dolama, Mohammad, Sopena, Eric (2005)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity: