BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
In this work, we present a generalization of Gale's lemma. Using this generalization, we introduce two combinatorial sharp lower bounds for conid(B0(G))+1 and conid(B(G))+2, two famous topological lower bounds for the chromatic number of a graph G.
Recently, Kupavskii~[{\it On random subgraphs of {K}neser and {S}chrijver graphs. J. Combin. Theory Ser. A, {\rm 2016}.}] investigated the chromatic number of random Kneser graphs $\KG_{n,k}(ρ)$ and proved that, in many cases, the chromatic numbers of the random Kneser graph $\KG_{n,k}(ρ)$ and the Kneser graph $\KG_{n,k}$ are almost surely closed. He also marked the studying of the chromatic number of random Kneser hypergraphs $\KG^r_{n,k}(ρ)$ as a very interesting problem. With the help of Zp-Tucker lemma, a combinatorial generalization of the Borsuk-Ulam theorem, we generalize Kupavskii's result to random general Kneser hypergraphs by introducing an almost surely lower bound for the chromatic number of them. Roughly speaking, as a special case of our result, we show that the chromatic numbers of the random Kneser hypergraph $\KG^r_{n,k}(ρ)$ and the Kneser hypergraph $\KG^r_{n,k}$ are almost surely closed in many cases. Moreover, restricting to the Kneser and {S}chrijver graphs, we present a purely combinatorial proof for an improvement of Kupavskii's results. Also, for any hypergraph $\HH$, we present a lower bound for the minimum number of colors required in a coloring of $\KG^r(\mathcal{H})$ with no monochromatic Kt,…,tr subhypergraph, where Kt,…,tr is the complete r-uniform r-partite hypergraph with tr vertices such that each of its parts has t vertices. This result generalizes the lower bound for the chromatic number of $\KG^r(\mathcal{H})$ found by the present authors~[{\it On the chromatic number of general {K}neser hypergraphs. J. Combin. Theory, Ser. B, {\rm 2015}.}].
A 50 years unsolved conjecture by Hedetniemi [{\it Homomorphisms of graphs and automata, \newblock {\em Thesis (Ph.D.)--University of Michigan}, 1966}] asserts that the chromatic number of the categorical product of two graphs G and H is min{χ(G),χ(H)}. The present authors [{\it On the chromatic number of general {K}neser hypergraphs. \newblock {\em Journal of Combinatorial Theory, Series B}, 2015.}] introduced the altermatic and the strong altermatic number of graphs as two tight lower bounds for the chromatic number of graphs. In this work, we prove a relaxation of Hedetniemi's conjecture in terms of strong altermatic number. Also, we present a tight lower bound for the chromatic number of the categorical product of two graphs in term of their altermatic and strong altermatic numbers. These results enrich the family of pair graphs {G,H} satisfying Hedetniemi's conjecture.
In view of Tucker's lemma (an equivalent combinatorial version of the Borsuk- Ulam theorem), the present authors (2013) introduced the kth altermatic number of a graph G as a tight lower bound for the chromatic number of G. In this note, we present a purely combinatorial proof for this result.
A Kneser representation KG(H) for a graph G is a bijective assignment of hyperedges of a hypergraph H to the vertices of G such that two vertices of G are adjacent if and only if the corresponding hyperedges are disjoint. In this paper, we introduce a colored version of the Turan number and use that to determine the chromatic number of some families of graphs in terms of the generalized Turan number of graphs. In particular, we determine the chromatic number of every Kneser multigraph KG(H), where the vertex set of H is the edge set of a multigraph G such that the multiplicity of each edge is greater than 1 and a hyperedge in H corresponds to a subgraph of G isomorphic to some graph in a fixed prescribed family of simple graphs.
For a graph G, the tree graph TG,t has all tree subgraphs of G with t vertices as vertex set and two tree subgraphs are neighbors if they are edge-disjoint. Also, the rth cut number of G is the minimum number of edges between parts of a partition of vertex set of G into two parts such that each part has size at least r. We show that if t=(1−o(1))n and n is large enough, then for any dense graph G with n vertices, the chromatic number of the tree graph TG,t is equal to the (n−t+1)th cut number of G. In particular, as a consequence, we prove that if n is large enough and G is a dense graph, then the chromatic number of the spanning tree graph TG,n is equal to the size of the minimum cut of G. The proof method is based on alternating Turán number inspired by Tucker's lemma, an equivalent combinatorial version of the Borsuk-Ulam theorem.
In an earlier paper, the present authors (2013) introduced the altermatic number of graphs and used Tucker's Lemma, an equivalent combinatorial version of the Borsuk-Ulam Theorem, to show that the altermatic number is a lower bound for the chromatic number. A matching graph has the set of all matchings of a specified size of a graph as vertex set and two vertices are adjacent if the corresponding matchings are edge-disjoint. It is known that the Kneser graphs, the Schrijver graphs, and the permutation graphs can be represented by matching graphs. In this paper, as a generalization of the well-known result of Schrijver about the chromatic number of Schrijver graphs, we determine the chromatic number of a large family of matching graphs by specifying their altermatic number. In particular, we determine the chromatic number of these matching graphs in terms of the generalized Turan number of matchings.
In this paper we consider higher isoperimetric numbers of a (finite directed) graph. In this regard we focus on the nth mean isoperimetric constant of a directed graph as the minimum of the mean outgoing normalized flows from a given set of n disjoint subsets of the vertex set of the graph. We show that the second mean isoperimetric constant in this general setting, coincides with (the mean version of) the classical Cheeger constant of the graph, while for the rest of the spectrum we show that there is a fundamental difference between the nth isoperimetric constant and the number obtained by taking the minimum over all n-partitions. In this direction, we show that our definition is the correct one in the sense that it satisfies a Federer-Fleming-type theorem, and we also define and present examples for the concept of a supergeometric graph as a graph whose mean isoperimetric constants are attained on partitions at all levels. Moreover, considering the NP-completeness of the isoperimetric problem on graphs, we address ourselves to the approximation problem where we prove general spectral inequalities that give rise to a general Cheeger-type inequality as well. On the other hand, we also consider some algorithmic aspects of the problem where we show connections to orthogonal representations of graphs and following J.~Malik and J.~Shi (2000) we study the close relationships to the well-known k-means algorithm and normalized cuts method.
One of the most famous conjecture in graph theory is Hedetniemi's conjecture stating that the chromatic number of the categorical product of graphs is the minimum of their chromatic numbers. Using a suitable extension of the definition of the categorical product, Zhu proposed in 1992 a similar conjecture for hypergraphs. We prove that Zhu's conjecture is true for the usual Kneser hypergraphs of same rank. It provides to the best of our knowledge the first non-trivial and explicit family of hypergraphs with rank larger than two satisfying this conjecture (the rank two case being Hedetniemi's conjecture). We actually prove a more general result providing a lower bound on the chromatic number of the categorical product of any Kneser hypergraphs as soon as they all have same rank. We derive from it new families of graphs satisfying Hedetniemi's conjecture. The proof of the lower bound relies on the Zp-Tucker lemma.
In this paper, in view of Zp-Tucker lemma, we introduce a lower bound for chromatic number of Kneser hypergraphs which improves Dol'nikov-K{ř}{\'ı}{ž} bound. Next, we introduce multiple Kneser hypergraphs and we specify the chromatic number of some multiple Kneser hypergraphs. For a vector of positive integers s=(s1,s2,…,sm) and a partition π=(P1,P2,…,Pm) of {1,2,…,n}, the multiple Kneser hypergraph KGr(π;s;k) is a hypergraph with the vertex set V={A: A⊆P1∪P2∪⋯∪Pm, ∣A∣=k,∀1≤i≤m; ∣A∩Pi∣≤si} whose edge set is consist of any r pairwise disjoint vertices. We determine the chromatic number of multiple Kneser hypergraphs provided that r=2 or for any 1≤i≤m, we have ∣Pi∣≤2si. A subset S⊆[n] is almost s-stable if for any two distinct elements i,j∈S, we have ∣i−j∣≥s. The almost s-stable Kneser hypergraph KGr(n,k)s−stab∼ has all s-stable subsets of [n] as the vertex set and every r-tuple of pairwise disjoint vertices forms an edge. Meunier [The chromatic number of almost stable Kneser hypergraphs. J. Combin. Theory Ser. A, 118(6):1820--1828, 2011] showed for any positive integer r, χ(KGr(n,k)2−stab∼)=⌈r−1n−r(k−1)⌉. We extend this result to a large family of Schrijver hypergraphs. Finally, we present a colorful-type result which confirms the existence of a completely multicolored complete bipartite graph in any coloring of a graph.
For a binary code Γ of length v, a v-word w produces by a set of codewords {w1,...,wr}⊆Γ if for all i=1,...,v, we have wi∈{wi1,...,wir} . We call a code r-secure frameproof of size t if ∣Γ∣=t and for any v-word that is produced by two sets C1 and C2 of size at most r then the intersection of these sets is nonempty. A d-biclique cover of size v of a graph G is a collection of v-complete bipartite subgraphs of G such that each edge of G belongs to at least d of these complete bipartite subgraphs. In this paper, we show that for t≥2r, an r-secure frameproof code of size t and length v exists if and only if there exists a 1-biclique cover of size v for the Kneser graph KG(t,r) whose vertices are all r-subsets of a t-element set and two r-subsets are adjacent if their intersection is empty. Then we investigate some connection between the minimum size of d-biclique covers of Kneser graphs and cover-free families, where an (r,w;d) cover-free family is a family of subsets of a finite set such that the intersection of any r members of the family contains at least d elements that are not in the union of any other w members. Also, we present an upper bound for 1-biclique covering number of Kneser graphs.
This paper studies some coloring properties of graph powers. We show that χc(G2s+12r+1)=(s−r)χc(G)+2r+1(2s+1)χc(G) provided that χc(G2s+12r+1)<4. As a consequence, one can see that if 2s+12r+1≤3(χc(G)−2)χc(G), then χc(G2s+12r+1)=(s−r)χc(G)+2r+1(2s+1)χc(G). In particular, χc(K3n+131)=3n+29n+3 and K3n+131 has no subgraph with circular chromatic number equal to 2n+16n+1. This provides a negative answer to a question asked in [Xuding Zhu, Circular chromatic number: a survey, Discrete Math., 229(1-3):371--410, 2001]. Also, we present an upper bound for the fractional chromatic number of subdivision graphs. Precisely, we show that χf(G2s+11)≤sχf(G)+1(2s+1)χf(G). Finally, we investigate the nth multichromatic number of subdivision graphs.
An (r,w;d) cover-free family (CFF) is a family of subsets of a finite set such that the intersection of any r members of the family contains at least d elements that are not in the union of any other w members. The minimum number of elements for which there exists an (r,w;d)−CFF with t blocks is denoted by N((r,w;d),t). In this paper, we show that the value of N((r,w;d),t) is equal to the d-biclique covering number of the bipartite graph It(r,w) whose vertices are all w- and r-subsets of a t-element set, where a w-subset is adjacent to an r-subset if their intersection is empty. Next, we introduce some new bounds for N((r,w;d),t). For instance, we show that for r≥w and r≥2 N((r,w;1),t)≥clogr(w+1r+w)+(w+1r+w−1)+3(w−2r+w−4)log(t−w+1), where c is a constant satisfies the well-known bound N((r,1;1),t)≥clogrr2logt. Also, we determine the exact value of N((r,w;d),t) for some values of d. Finally, we show that N((1,1;d),4d−1)=4d−1 whenever there exists a Hadamard matrix of order 4d.
We investigate some coloring properties of Kneser graphs. A star-free coloring is a proper coloring c:V(G)→N such that no path with three vertices may be colored with just two consecutive numbers. The minimum positive integer t for which there exists a star-free coloring c:V(G)→{1,2,...,t} is called the star-free chromatic number of G and denoted by χs(G). In view of Tucker-Ky Fan's lemma, we show that for any Kneser graph KG(n,k) we have χs(KG(n,k))≥max{2χ(KG(n,k))−10,χ(KG(n,k))} where n≥2k≥4. Moreover, we show that χs(KG(n,k))=2χ(KG(n,k))−2=2n−4k+2 provided that n≤38k. This gives a partial answer to a conjecture of [12]. Also, we conjecture that for any positive integers n≥2k≥4 we have χs(KG(n,k))=2χ(KG(n,k))−2.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.