Search

In this paper, we use methods from spectral graph theory to obtain some results on the sum–product problem over finite valuation rings R of order q r which generalize recent results given by Hegyvári and Hennecart (2013). More precisely, we prove that, for related pairs of two-variable functions f ( x , y ) and g ( x , y ) , if A and B are two sets in R ∗ with | A | = | B | = q α , then max { | f ( A , B ) | , | g ( A , B ) | } ≫ | A | 1 + Δ ( α ) , for some Δ ( α ) > 0 . [ABSTRACT FROM AUTHOR]

In a recent paper Kwon and Oum (2014), Kwon and Oum claim that every graph of bounded rank-width is a pivot-minor of a graph of bounded tree-width (while the converse has been known true already before). We study the analogous questions for “depth” parameters of graphs, namely for the tree-depth and related new shrub-depth. We show how a suitable adaptation of known results implies that shrub-depth is monotone under taking vertex-minors, and we prove that every graph class of bounded shrub-depth can be obtained via vertex-minors of graphs of bounded tree-depth. While we exhibit an example that pivot-minors are generally not sufficient (unlike Kwon and Oum (2014)) in the latter statement, we then prove that the bipartite graphs in every class of bounded shrub-depth can be obtained as pivot-minors of graphs of bounded tree-depth. [ABSTRACT FROM AUTHOR]

Abstract: Consider a graph and, for each vertex , a subset of neighbors of . A -coloring is a coloring of the elements of so that vertices appearing together in some receive pairwise distinct colors. An obvious lower bound for the minimum number of colors in such a coloring is the maximum size of a set , denoted by . In this paper we study graph classes for which there is a function , such that for any graph and any , there is a -coloring using at most colors. It is proved that if such a function exists for a class , then can be taken to be a linear function. It is also shown that such classes are precisely the classes having bounded star chromatic number. We also investigate the list version and the clique version of this problem, and relate the existence of functions bounding those parameters to the recently introduced concepts of classes of bounded expansion and nowhere-dense classes. [Copyright &y& Elsevier]

Abstract: Let be a graph. A clique-transversal set is a subset of vertices of such that meets all cliques of , where a clique is defined as a complete subgraph maximal under inclusion and having at least two vertices. The clique-transversal number, denoted by , of is the cardinality of a minimum clique-transversal set in . A -clique-coloring of is a -coloring of its vertices such that no clique is monochromatic. All planar graphs have been proved to be 3-clique-colorable by Mohar and Škrekovski [B. Mohar, R. Škrekovski, The Grötzsch theorem for the hypergraph of maximal cliques, Electron. J. Combin. 6 (1999) #R26]. Erdős et al. [P. Erdős, T. Gallai, Zs. Tuza, Covering the cliques of a graph with vertices, Discrete Math. 108 (1992) 279–289] proposed to find sharp estimates on for planar graphs. In this paper we first show that every outerplanar graph of order has and the bound is tight. Secondly, we prove that every claw-free planar graph different from an odd cycle is -clique-colorable and we present a polynomial-time algorithm to find the -clique-coloring. As a by-product of the result, we obtain a tight upper bound on the clique-transversal number for claw-free planar graphs. [Copyright &y& Elsevier]

Abstract: A dominating set of graph is called metric-locating–dominating if it is also locating, that is, if every vertex is uniquely determined by its vector of distances to the vertices in . If moreover, every vertex not in is also uniquely determined by the set of neighbors of belonging to , then it is said to be locating–dominating. Locating, metric-locating–dominating and locating–dominating sets of minimum cardinality are called -codes, -codes and -codes, respectively. A Nordhaus–Gaddum bound is a tight lower or upper bound on the sum or product of a parameter of a graph and its complement . In this paper, we present some Nordhaus–Gaddum bounds for the location number , the metric-location–domination number and the location–domination number . Moreover, in each case, the graph family attaining the corresponding bound is fully characterized. [Copyright &y& Elsevier]

A hypergraph is -colorable if there is a -coloring of the vertices with no monochromatic hyperedge. Let denote the class of all -uniform -regular hypergraphs. The Lovász Local Lemma, devised by Erdös and Lovász in 1975 to tackle the problem of hypergraph 2-colorings, implies that every hypergraph is -colorable, provided . Alon and Bregman [N. Alon, Z. Bregman, Every 8-uniform 8-regular hypergraph is 2-colorable, Graphs Combin. 4 (1988) 303–306] proved the slightly stronger result that every hypergraph is -colorable, provided . It is implicitly known in the literature that the Alon–Bregman result is true for all , as remarked by Vishwanathan [S. Vishwanathan, On 2-coloring certain -uniform hypergraphs, J. Combin. Theory Ser. A 101 (2003) 168–172] even though we have not seen it explicitly proved. For completeness, we provide a short proof of this result. As remarked by Alon and Bregman the result is not true when , as may be seen by considering the Fano plane. Our main result in this paper is a strengthening of the above results. For this purpose, we define a set of vertices in a hypergraph to be a free set in if we can -color such that every edge in receives at least one vertex of each color. Equivalently, is a free set in if it is the complement of two disjoint transversals in . For every , we prove that every hypergraph of order has a free set of size at least . For any where and for sufficiently large , we prove that every hypergraph of order has a free set of size at least , where , and so as . As an application, we show that the total restrained domination number of a graph on vertices with sufficiently large minimum degree is at most , which significantly improves the best known bound of . [ABSTRACT FROM AUTHOR]