4 results on '"Gyárfás, András"'
Search Results
2. Proper edge colorings of planar graphs with rainbow $C_4$-s
- Author
-
Gyárfás, András, Martin, Ryan R., Ruszinkó, Miklós, and Sárközy, Gábor N.
- Subjects
Mathematics - Combinatorics - Abstract
We call a proper edge coloring of a graph $G$ a B-coloring if every 4-cycle of $G$ is colored with four different colors. Let $q_B(G)$ denote the smallest number of colors needed for a B-coloring of $G$. Motivated by earlier papers on B-colorings, here we consider $q_B(G)$ for planar and outerplanar graphs in terms of the maximum degree $\Delta = \Delta(G)$. We prove that $q_B(G)\le 2\Delta+8$ for planar graphs, $q_B(G)\le 2\Delta$ for bipartite planar graphs and $q_B(G)\le \Delta+1$ for outerplanar graphs with $\Delta \ge 4$. We conjecture that, for $\Delta$ sufficiently large, $q_B(G)\le 2\Delta(G)$ for planar $G$ and $q_B(G)\le \Delta(G)$ for outerplanar $G$., Comment: 15 pages, 4 figures, to appear in Journal of Graph Theory
- Published
- 2024
- Full Text
- View/download PDF
3. Clique covers of complete graphs and piercing multitrack intervals
- Author
-
Barát, János, Gyárfás, András, and Sárközy, Gábor N.
- Subjects
Mathematics - Combinatorics ,05C62, 05D10 - Abstract
Assume that $R_1,R_2,\dots,R_t$ are disjoint parallel lines in the plane. A $t$-interval (or $t$-track interval) is a set that can be written as the union of $t$ closed intervals, each on a different line. It is known that pairwise intersecting $2$-intervals can be pierced by two points, one from each line. However, it is not true that every set of pairwise intersecting $3$-intervals can be pierced by three points, one from each line. For $k\ge 3$, Kaiser and Rabinovich asked whether $k$-wise intersecting $t$-intervals can be pierced by $t$ points, one from each line. Our main result provides an asymptotic answer: in any set $S_1,\dots,S_n$ of $k$-wise intersecting $t$-intervals, at least $\frac{k-1}{k+1}n$ can be pierced by $t$ points, one from each line. We prove this in a more general form, replacing intervals by subtrees of a tree. This leads to questions and results on covering vertices of edge-colored complete graphs by vertices of monochromatic cliques having distinct colors, where the colorings are chordal, or more generally induced $C_4$-free graphs. For instance, we show that if the edges of a complete graph $K_n$ are colored with red or blue so that both color classes are induced $C_4$-free, then at least ${4n\over 5}$ vertices can be covered by a red and a blue clique, and this is best possible. We conclude by pointing to new Ramsey-type problems emerging from these restricted colorings., Comment: 15 pages, 3 figures
- Published
- 2024
4. Monochromatic spanning trees and matchings in ordered complete graphs.
- Author
-
Barát, János, Gyárfás, András, and Tóth, Géza
- Subjects
- *
RAMSEY numbers , *COMPLETE graphs , *SPANNING trees , *SUBGRAPHS - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.