Marking Games and the Oriented Game Chromatic Number of Partial <Emphasis Type="Italic">k</Emphasis>-Trees

 Nešetřil and Sopena introduced the concept of oriented game chromatic number. They asked whether the oriented game chromatic number of partial k-trees was bounded. Here we answer their question positively. Received: January 12, 2001 Final version received: February 25, 2002     

On-line arbitrarily vertex decomposable trees

A tree T is arbitrarily vertex decomposable if for any sequence τ of positive integers adding up to the order of T there is a sequence of vertex-disjoint subtrees of T whose orders are given by τ. An on-line version of the problem of characterizing arbitrarily vertex decomposable trees is completely solved here.     

Degree Sums and Covering Cycles

It is shown that if in a simple graph G of order n the sum of degrees of any three pairwise non-adjacent vertices is at least n, then there are two cycles (or one cycle and an edge or a vertex) of GF that contain all the vertices. © 1995 John Wiley & Sons, Inc.     

Contractions and minimalk-colorability

Coloring the vertex set of a graphG with positive integers, thechromatic sum (G) ofG is the minimum sum of colors in a proper coloring. Thestrength ofG is the largest integer that occurs in every coloring whose total is(G). Proving a conjecture of Kubicka and Schwenk, we show that every tree of strengths has at least ((2 + ) ^s–1 – (2 – ) ^s–1)/ vertices (s 2). Surprisingly, this extremal result follows from a topological property of trees. Namely, for everys 3 there exist precisely two treesT _s andR _s such that every tree of strength at leasts is edge-contractible toT _s orR _s .     

Sub-Ramsey numbers for arithmetic progressions

Letm 3 andk 1 be two given integers. Asub-k-coloring of [n] = {1, 2,...,n} is an assignment of colors to the numbers of [n] in which each color is used at mostk times. Call an arainbow set if no two of its elements have the same color. Thesub-k-Ramsey number sr(m, k) is defined as the minimumn such that every sub-k-coloring of [n] contains a rainbow arithmetic progression ofm terms. We prove that((k – 1)m ²/logmk) sr(m, k) O((k – 1)m ² logmk) asm , and apply the same method to improve a previously known upper bound for a problem concerning mappings from [n] to [n] without fixed points.Research supported in part by Allon Fellowship and by a Bat Sheva de-Rothschild grant.Research supported in part by the AKA Research Fund of the Hungarian Academy of Sciences, grant No. 1-3-86-264.     

Intersection Dimensions of Graph Classes

The intersection dimension of a graphG with respect to a classA of graphs is the minimumk such thatG is the intersection of at mostk graphs on vertex setV(G) each of which belongs toA. We consider the question when the intersection dimension of a certain family of graphs is bounded or unbounded. Our main results are (1) ifA is hereditary, i.e., closed on induced subgraphs, then the intersection dimension of all graphs with respect toA is unbounded, and (2) the intersection dimension of planar graphs with respect to the class of permutation graphs is bounded. We also give a simple argument based on [Ben-Arroyo Hartman, I., Newman, I., Ziv, R.:On grid intersection graphs, Discrete Math.87 (1991) 41-52] why the boxicity (i.e., the intersection dimension with respect to the class of interval graphs) of planar graphs is bounded. Further we study the relationships between intersection dimensions with respect to different classes of graphs.     

Maximum number of colors: C-coloring and related problems

We discuss problems and results on the maximum number of colors in combinatorial structures under the assumption that no totally multicolored sets of a specified type occur.     

Local and global average degree in graphs and multigraphs

A vertex v of a graph G is called groupie if the average degree t_v of all neighbors of v in G is not smaller than the average degree t_G of G. Every graph contains a groupie vertex; the problem of whether or not every simple graph on ≧2 vertices has at least two groupie vertices turned out to be surprisingly difficult. We present various sufficient conditions for a simple graph to contain at least two groupie vertices. Further, we investigate the function f(n) = max min_v (t_v/t_G), where the maximum ranges over all simple graphs on n vertices, and prove that f(n) = 1/42n + o(1). The corresponding result for multigraphs is in sharp contrast with the above. We also characterize trees in which the local average degree t_v is constant.     

Minimal colorings for properly colored subgraphs

We give conditions on the minimum numberk of colors, sufficient for the existence of given types of properly edge-colored subgraphs in ak-edge-colored complete graph. The types of subgraphs we study include families of internally pairwise vertex-disjoint paths with common endpoints, hamiltonian paths and hamiltonian cycles, cycles with a given lower bound of their length, spanning trees, stars, and cliques. Throughout the paper, related conjectures are proposed.Research supported by a European Union PECO grant under identification number CIPA3510PL929589, while on leave at University Paris-XI