On n-stars in colorings and orientations of graphs
An n-star S in a graph G is the union of geodesic intervals I1,…,Ik with common end O such that the subgraphs I1∖{O},…,Ik∖{O} are pairwise disjoint and l(I1)+…+l(Ik)=n. If the edges of G are oriented, S is directed if each ray Ii is directed. For natural number n,r, we construct a graph G of diam(G)...
Gespeichert in:
| Datum: | 2016 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2016
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/155731 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | On n-stars in colorings and orientations of graphs / I.V. Protasov // Algebra and Discrete Mathematics. — 2016. — Vol. 22, № 2. — С. 301-303. — Бібліогр.: 3 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-155731 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1557312019-06-18T01:26:45Z On n-stars in colorings and orientations of graphs Protasov, I.V. An n-star S in a graph G is the union of geodesic intervals I1,…,Ik with common end O such that the subgraphs I1∖{O},…,Ik∖{O} are pairwise disjoint and l(I1)+…+l(Ik)=n. If the edges of G are oriented, S is directed if each ray Ii is directed. For natural number n,r, we construct a graph G of diam(G)=n such that, for any r-coloring and orientation of E(G), there exists a directed n-star with monochrome rays of pairwise distinct colors. 2016 Article On n-stars in colorings and orientations of graphs / I.V. Protasov // Algebra and Discrete Mathematics. — 2016. — Vol. 22, № 2. — С. 301-303. — Бібліогр.: 3 назв. — англ. 1726-3255 2010 MSC:05C55. http://dspace.nbuv.gov.ua/handle/123456789/155731 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
An n-star S in a graph G is the union of geodesic intervals I1,…,Ik with common end O such that the subgraphs I1∖{O},…,Ik∖{O} are pairwise disjoint and l(I1)+…+l(Ik)=n. If the edges of G are oriented, S is directed if each ray Ii is directed. For natural number n,r, we construct a graph G of diam(G)=n such that, for any r-coloring and orientation of E(G), there exists a directed n-star with monochrome rays of pairwise distinct colors. |
| format |
Article |
| author |
Protasov, I.V. |
| spellingShingle |
Protasov, I.V. On n-stars in colorings and orientations of graphs Algebra and Discrete Mathematics |
| author_facet |
Protasov, I.V. |
| author_sort |
Protasov, I.V. |
| title |
On n-stars in colorings and orientations of graphs |
| title_short |
On n-stars in colorings and orientations of graphs |
| title_full |
On n-stars in colorings and orientations of graphs |
| title_fullStr |
On n-stars in colorings and orientations of graphs |
| title_full_unstemmed |
On n-stars in colorings and orientations of graphs |
| title_sort |
on n-stars in colorings and orientations of graphs |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2016 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/155731 |
| citation_txt |
On n-stars in colorings and orientations of graphs / I.V. Protasov // Algebra and Discrete Mathematics. — 2016. — Vol. 22, № 2. — С. 301-303. — Бібліогр.: 3 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT protasoviv onnstarsincoloringsandorientationsofgraphs |
| first_indexed |
2025-07-14T07:58:17Z |
| last_indexed |
2025-07-14T07:58:17Z |
| _version_ |
1837608363565776896 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 22 (2016). Number 2, pp. 301–303
© Journal “Algebra and Discrete Mathematics”
On n-stars in colorings
and orientations of graphs
Igor Protasov
Abstract. An n-star S in a graph G is the union of geodesic
intervals I1, . . . , Ik with common end O such that the subgraphs
I1 \{O}, . . . , Ik \{O} are pairwise disjoint and l(I1)+. . .+l(Ik) = n.
If the edges of G are oriented, S is directed if each ray Ii is directed.
For natural number n, r, we construct a graph G of diam(G) = n
such that, for any r-coloring and orientation of E(G), there exists a
directed n-star with monochrome rays of pairwise distinct colors.
Let G be a finite connected graph (with the set of vertices V (G) and
the set of edges E(G)) endowed with the path metric d (d(u, v) is the
length of a shortest path between u and v). A path v0v1 . . . vn is called a
geodesic interval if d(v0, vn) = n.
For a natural number n, we say that a subgraph S of G is an n-star
centered at the vertex O if S is the union of geodesic intervals I1, . . . , Ik
with common end O such that the subgraphs I1 \ {O}, . . . , Ik \ {O} are
pairwise disjoint and l(I1) + . . . + l(Ik) = n, l(Ii) > 0, i ∈ {1, . . . , k},
where l(I) is the length of I. Each Ii is called a ray of S. We say that S
is isometrically embedded (in G) if for any two vertices u, v of S, d(u, v)
is equal to the distance between u and v inside S.
If each edge from E(G) is oriented, we say that S is directed if each
edge vivi+1 in its ray v0 . . . vt is oriented as −−−→vivi+1.
We recall that diam(G) is the length of a longest geodesic interval in
G, and introduce directed and chromatic diameters by
diam(G) := maximal p such that, in each orientation of E(G), there
is a directed geodesic interval of length p;
2010 MSC: 05C55.
Key words and phrases: n-star, coloring, orientation.
302 On n-stars in colorings and orientations of graphs
r-diam(G) := maximal p such that, in each r-coloring of E(G), there
is a monochrome interval of length p.
Theorem 1. For any natural numbers n, r, there exists a graph G of
diam(G) = n such that, for any r-coloring and orientation of E(G), there
is a directed isometrically embedded n-star S with monochrome rays of
pairwise distinct colors. In particular,
−−−→
diam(G) = n and r-diam(G) > n/r.
Proof. We fix r and proceed by induction on n. For n = 1, we take
G = K2, the complete graph with two vertices.
We assume that a graph G satisfies the conclusion for some n. We put
m = r|E(G)| 2|E(G)| + 1 and consider the Cartesian product H = G × Km,
V (H) = V (G)×V (Km) and (a, c)(b, d) ∈ E(H) if and only if either a = b
or c = d and ab ∈ E(G).
Now we take arbitrary orientation O of E(H) and coloring χ : E(H) →
{1, . . . , r}. By the choice of m there are c, d ∈ V (Km) such that the
restrictions of χ and O onto G × {c}, G × {d} coincide.
By the inductive assumption, there is an n-star S in G centered at
O such that the n-star S × {c} is directed and has monochrome rays of
pairwise distinct colors. We suppose that the edge (O, c)(O, d) is directed
from (O, c) to (O, d) (the opposite case is analogous), look at the color
i = χ((O, c)(O, d)) and replace the ray of color i in S × {c} with the ray
(O, c)(O, d)I, where I is the ray of color i in S × {d}. After that, we get
the desired (n + 1)-star in H.
By the construction, G is the Cartesian product of n complete graphs.
Analyzing the proof with vertex-colorings in place of edge-colorings, we
get
Theorem 2. For any natural numbers n, r, there exists a graph G of
diam(G) = n such that, for any r-coloring of V (G) and orientation of
E(G), there is a directed monochrome geodesic interval of length n − 1.
Comments. The story began when Taras Banakh transferred me the
following question of Krzysztof Pszczoła: can every graph be oriented
so that each directed path v0v1v2v3 has the shortcut −−→v0v2 or −−→v1v3. In
the case r = 1, Theorem 1 gives maximally negative answer to this
question (perhaps, motivated by comparability graphs ). We mention
only three somehow related results from Ramsey Graph Theory. For every
acyclic directed graph G, there exists [1] a graph H such that, for every
orientation of E(H), there is an induced copy of G. In the case G is a
tree, see [3] for bounds on | V (H) | and | E(H) | . For every graph G and
I . Protasov 303
a natural number r, there exists a graph H such that, for every r-coloring
of E(H), there is a monochrome isometric copy of G. This statement can
be extracted from Theorem 3.1 in [2].
Applying above Ramsey-isometric fact and Theorem 2, we conclude:
For any natural numbers m, r, there exists a graph H such that, for
every r-coloring of E(H), every r-coloring of V (H) and any orientation of
E(H), there is a directed, edge-monochrome, vertex-monochrome geodesic
interval of length m.
Acknowledgement
I thank Taras Banakh and Oleg Pikhurko for infosupport and discus-
sions roundabout this note.
References
[1] M. Cochand, P. Duchet, A few remarks on orientations of graphs and Ramsey
theory, in: Irregularities of Partitions, Algorithms and Combinatorics 8 (eds. Halasz,
G., and Sos, V.T.) Springer-Verlag, Berlin (1989), 39-46.
[2] J. Nešetril, V. Rödl, Sparse Ramsey graphs, Combinatorica 4: 1 (1984) 71-78.
[3] I. Kohayakawa, T. Łuczak, V. Rödl, Ramsey-type results for oriented trees, J. Graph
Theory 22: 1 (1996) 1-8.
Contact information
I. Protasov Department of Cybernetics, Kyiv University,
Volodymyrska 64, 01033, Kyiv Ukraine
E-Mail(s): i.v.protasov@gmail.com
Received by the editors: 30.09.2016
and in final form 03.10.2016.
|