Search

We call a proper edge coloring of a graph G $G$ a B‐coloring if every 4‐cycle of G $G$ is colored with four different colors. Let qB(G) ${q}_{B}(G)$ denote the smallest number of colors needed for a B‐coloring of G $G$. Motivated by earlier papers on B‐colorings, here we consider qB(G) ${q}_{B}(G)$ for planar and outerplanar graphs in terms of the maximum degree Δ=Δ(G) ${\rm{\Delta }}={\rm{\Delta }}(G)$. We prove that qB(G)≤2Δ+8 ${q}_{B}(G)\le 2{\rm{\Delta }}+8$ for planar graphs, qB(G)≤2Δ ${q}_{B}(G)\le 2{\rm{\Delta }}$ for bipartite planar graphs, and qB(G)≤Δ+1 ${q}_{B}(G)\le {\rm{\Delta }}+1$ for outerplanar graphs with Δ≥4 ${\rm{\Delta }}\ge 4$. We conjecture that, for Δ ${\rm{\Delta }}$ sufficiently large, qB(G)≤2Δ(G) ${q}_{B}(G)\le 2{\rm{\Delta }}(G)$ for planar G $G$, and qB(G)≤Δ(G) ${q}_{B}(G)\le {\rm{\Delta }}(G)$ for outerplanar G $G$. [ABSTRACT FROM AUTHOR]

We study two well‐known Ramsey‐type problems for (vertex‐)ordered complete graphs. Two independent edges in ordered graphs can be nested, crossing, or separated. Apart from two trivial cases, these relations define six types of subgraphs, depending on which one (or two) of these relations are forbidden. Our first target is to refine a remark by Erdős and Rado that every 2‐coloring of the edges of a complete graph contains a monochromatic spanning tree. We show that forbidding one relation we always have a monochromatic (nonnested, noncrossing, and nonseparated) spanning tree in a 2‐edge‐colored ordered complete graph. On the other hand, if two relations are forbidden, then it is possible that we have monochromatic (nested, separated, and crossing) subtrees of size only ~n∕2 $\unicode{x0007E}n\unicode{x02215}2$ in a 2‐colored ordered complete graph on n $n$ vertices. Some of these results relate to drawings of complete graphs. For instance, the existence of a monochromatic nonnested spanning tree in 2‐colorings of ordered complete graphs verifies a more general conjecture for twisted drawings. Our second subject is to refine the Ramsey number of matchings, that is, pairwise independent edges for ordered complete graphs. Cockayne and Lorimer proved that for given positive integers t,n $t,n$, m=(t−1)(n−1)+2n $m=(t-1)(n-1)+2n$ is the smallest integer with the following property: every t $t$‐coloring of the edges of a complete graph Km ${K}_{m}$ contains a monochromatic matching with n $n$ edges. We conjecture that this result can be strengthened: t $t$‐colored ordered complete graphs on m $m$ vertices contain monochromatic nonnested and also nonseparated matchings with n $n$ edges. We prove this conjecture for some special cases including the following. (i) Every t $t$‐colored ordered complete graph on t+3 $t+3$ vertices contains a monochromatic nonnested matching of size two (n=2 $n=2$ case). We prove it by showing that the chromatic number of the subgraph of the Kneser graph induced by the nonnested 2‐matchings in an ordered complete graph on t+3 $t+3$ vertices is (t+1) $(t+1)$‐chromatic.(ii) Every 2‐colored ordered complete graph on 3n−1 $3n-1$ vertices contains a monochromatic nonseparated matching of size n $n$ (t=2 $t=2$ case). This is the hypergraph analog of a result of Kaiser and Stehlík who proved that the Kneser graph induced by the nonseparated 2‐matchings in an ordered complete graph on t+3 $t+3$ vertices is (t+1) $(t+1)$‐chromatic. For nested, separated, and crossing matchings the situation is different. The smallest m $m$ ensuring a monochromatic matching of size n $n$ in every t $t$‐coloring is 2(t(n−1))+1) $2(t(n-1))+1)$ in the first two cases and one less in the third case. [ABSTRACT FROM AUTHOR]

A digraph is d $d$‐dominating if every set of at most d $d$ vertices has a common out‐neighbor. For all integers d≥2 $d\ge 2$, let f(d) $f(d)$ be the smallest integer such that the vertices of every 2‐edge‐colored (finite or infinite) complete digraph (including loops) can be covered by the vertices of at most f(d) $f(d)$ monochromatic d $d$‐dominating subgraphs. Note that the existence of f(d) $f(d)$ is not obvious – indeed, the question which motivated this paper was simply to determine whether f(d) $f(d)$ is bounded, even for d=2 $d=2$. We answer this question affirmatively for all d≥2 $d\ge 2$, proving 4≤f(2)≤8 $4\le f(2)\le 8$ and 2d≤f(d)≤2ddd−1d−1for alld≥3 $2d\le f(d)\le 2d\left(\frac{{d}^{d}-1}{d-1}\right)\,\,\text{for all}\,\,d\ge 3$. We also give an example to show that there is no analogous bound for more than two colors. Our result provides a positive answer to a question regarding an infinite analogue of the Burr‐Erdős conjecture on the Ramsey numbers of d $d$‐degenerate graphs. Moreover, a special case of our result is related to properties of d $d$‐paradoxical tournaments. [ABSTRACT FROM AUTHOR]

We call a partial Steiner triple system C (configuration) t-Ramsey if for large enough n (in terms of [ABSTRACT FROM AUTHOR]

We determine the 2-color Ramsey number of a connected triangle matching [ABSTRACT FROM AUTHOR]

A cross-free set of size m in a Steiner triple system [ABSTRACT FROM AUTHOR]

Let G=(V,E) be a τ‐critical graph with τ(G)=t. Erdős and Gallai proved that ∣V∣≤2t and the bound ∣E∣≤t+12 was obtained by Erdős, Hajnal, and Moon. We give here the sharp combined bound ∣E∣+∣V∣≤t+22 and find all graphs with equality. [ABSTRACT FROM AUTHOR]

Gallai-colorings of complete graphs-edge colorings such that no triangle is colored with three distinct colors-occur in various contexts such as the theory of partially ordered sets (in Gallai's original paper), information theory and the theory of perfect graphs. A basic property of Gallai-colorings with at least three colors is that at least one of the color classes must span a disconnected graph. We are interested here in whether this or a similar property remains true if we consider colorings that do not contain a rainbow copy of a fixed graph F. We show that such graphs F are very close to bipartite graphs, namely, they can be made bipartite by the removal of at most one edge. We also extend Gallai's property for two infinite families and show that it also holds when F is a path with at most six vertices. [ABSTRACT FROM AUTHOR]

Assume that D is a digraph without cyclic triangles and its vertices are partitioned into classes A1, ..., A t of independent vertices. A set is called a dominating set of size | S| if for any vertex there is a w∈ U such that ( w, v)∈ E( D). Let β( D) be the cardinality of the largest independent set of D whose vertices are from different partite classes of D. Our main result says that there exists a h = h(β( D)) such that D has a dominating set of size at most h. This result is applied to settle a problem related to generalized Gallai colorings, edge colorings of graphs without 3-colored triangles. © 2011 Wiley Periodicals, Inc. J Graph Theory [ABSTRACT FROM AUTHOR]

The Grundy number of a graph G is the largest k such that G has a greedy k-coloring, that is, a coloring with k colors obtained by applying the greedy algorithm according to some ordering of the vertices of G. In this article, we give new bounds on the Grundy number of the product of two graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:78-88, 2012 [ABSTRACT FROM AUTHOR]