A subgraph of an edge-colored graph is rainbow if all of its edges have different colors. For a graph H and a positive integer n, the anti-Ramsey number f(n,H) is the maximum number of colors in an edge-coloring of Kₙ with no rainbow copy of H. The rainbow number rb(n,H) is the minimum number of colors such that any edge-coloring of Kₙ with rb(n,H) number of colors contains a rainbow copy of H. Certainly rb(n,H) = f(n,H) + 1. Anti-Ramsey numbers were introduced by Erdös et al. [5] and studied in...

Let $r(G_1,G_2)$ be the Ramsey number of the two graphs $G_1$ and $G_2$. For $n_1\ge n_2\ge 1$ let $S(n_1,n_2)$ be the double star given by $V\left(S(n_1,n_2)\right)=\{v_0,v_1,...,v_{n_1},w_0$, $w_1,...,w_{n_2}\}$ and $E\left(S(n_1,n_2)\right)=\{v_0{v}_1,...,v_0{v}_{n_1},v_0{w}_0,w_0{w}_1,...,w_0{w}_{n_2}\}$. We determine $r(K_{1,m-1},$$S(n_1,...$

We survey recent developments on the Kakeya problem.[Proceedings of the 6th International Conference on Harmonic Analysis and Partial Differential Equations, El Escorial (Madrid), 2002].

Le système AutoGraphiX (AGX1 et AGX2) permet, parmi d’autres fonctions, la génération automatique de conjectures en théorie des graphes et, dans une version plus récente, la preuve automatique de conjectures simples. Afin d’illustrer ces fonctions et le type de résultats obtenus, nous étudions systématiquement ici des conjectures obtenues par ce système et de la forme ${\underline{b}}_n\le g\oplus i\le {\overline{b}}_n$ où $g$ désigne la maille (ou longueur du plus petit cycle) du graphe $G=(V,E)$, $i$ un autre invariant choisi parmi le nombre de stabilité,...

Le système AutoGraphiX (AGX1 et AGX2) permet, parmi d'autres fonctions, la génération automatique de conjectures en théorie des graphes et, dans une version plus récente, la preuve automatique de conjectures simples. Afin d'illustrer ces fonctions et le type de résultats obtenus, nous étudions systématiquement ici des conjectures obtenues par ce système et de la forme ${\underline{b}}_n\le g\oplus i\le {\overline{b}}_n$ où g désigne la maille (ou longueur du plus petit cycle) du graphe G=(V, E), i un autre invariant choisi parmi le nombre...

On étudie à l'aide du système AutoGraphiX 2 (AGX 2) des relations de la forme $${\underline{b}}_n\le g\oplus i\le {\overline{b}}_n$$ où g désigne la maille d'un graphe G=(V, E), i un autre invariant parmi la distance moyenne $\overline{l}$, l'index λ1, l'indice de Randić R et le nombre de domination β, $\oplus$ désigne l'une des opérations +, -, ×, /, ${\underline{b}}_n$ et ${\overline{b}}_n$ des fonctions de l'ordre n du graphe qui bornent l'expression $g\oplus i$ et sont atteintes pour tout n (sauf éventuellement de très petites valeurs du fait des effets de bord). Les résultats prouvés ou discutés ci-dessous...

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₅.

The restrained domination number ${\gamma }^r\left(G\right)$ and the total restrained domination number ${\gamma }_t^r\left(G\right)$ of a graph $G$ were introduced recently by various authors as certain variants of the domination number $\gamma \left(G\right)$ of $\left(G\right)$. A well-known numerical invariant of a graph is the domatic number $d\left(G\right)$ which is in a certain way related (and may be called dual) to $\gamma \left(G\right)$. The paper tries to define analogous concepts also for the restrained domination and the total restrained domination and discusses the sense of such new definitions.

We consider the problem of the existence of uniquely partitionable planar graphs. We survey some recent results and we prove the nonexistence of uniquely (𝓓₁,𝓓₁)-partitionable planar graphs with respect to the property 𝓓₁ "to be a forest".