In this note we describe how Lasoń's generalization of Alon's Combinatorial Nullstellensatz gives a framework for constructing lower bounds on the Turán number ex(n,Ks1,…,sr(r)) of the complete ...r-partite r-uniform hypergraph Ks1,…,sr(r). To illustrate the potential of this method, we give a short and simple explicit construction for the Erdős box problem, showing that ex(n,K2,…,2(r))=Ω(nr−1/r), which asymptotically matches best known bounds when r≤4.
Let G be a simple graph. Assume that c is a mapping from the edges of G to the set {1,2,…,k}. We say that c is neighbor sum distinguishing if every pair of vertex sums of adjacent vertices are ...pairwise distinct, where the vertex sum of a vertex is the sum of the colors on the edges incident to it. The least number k constructing such a coloring is denoted by χΣ′(G). We investigate the challenging conjecture presuming that χΣ′(G)≤Δ(G)+2 for any connected graph G≠C5, which is proposed by Flandrin et al. in 2012. We support this conjecture by proving that χΣ′(G)≤Δ(G)+⌈5col(G)+12⌉, which improves the previous bound Δ(G)+3col(G)−4 proved in Przybyło and Wong, 2015. Furthermore, our result holds for the list version.
For a signed graph Ġ=(G,σ), the net-degree of a vertex u in Ġ is the number of positive edges incident with u minus the number of negative edges incident with u, i.e., dĠ±(u)=dĠ+(u)−dĠ−(u). A ...zero net-regular signed graph, for short called zero net-regular graph, is a graph with a constant net-degree zero. Given an unsigned graph G, a map θ:V(G)→Z is called G-signed graphic if there is a sign function σ on G such that the resulting graph Ġ with θ(v)=dĠ±(v) for each vertex v. In this paper, our aim is to give characterizations for zero net-regular graph and its minimal nonempty structure, which originated from a study of a sequence being G-signed graphic. As a byproduct, using the Combinatorial Nullstellensatz Theorem, we give a simple condition for the existence of a nonempty zero net-regular subgraph in Ġ.
By a well-known theorem of Thomassen and a planar graph depicted by Voigt, we know that every planar graph is 5-choosable, and the bound is tight. In 1999, Lam, Xu and Liu reduced 5 to 4 on C4-free ...planar graphs. In the paper, by applying the famous Combinatorial Nullstellensatz, we design an effective algorithm to deal with list coloring problems. At the same time, we prove that a planar graph G is 4-choosable if any two 4-cycles having distance at least 5 in G, which extends the result of Lam et al.
Every nice graph is (1,5)-choosable Zhu, Xuding
Journal of combinatorial theory. Series B,
November 2022, 2022-11-00, Letnik:
157
Journal Article
Recenzirano
Odprti dostop
A graph G=(V,E) is total weight (k,k′)-choosable if the following holds: For any list assignment L which assigns to each vertex v a set L(v) of k real numbers, and assigns to each edge e a set L(e) ...of k′ real numbers, there is a proper L-total weighting, i.e., a map ϕ:V∪E→R such that ϕ(z)∈L(z) for z∈V∪E, and ∑e∈E(u)ϕ(e)+ϕ(u)≠∑e∈E(v)ϕ(e)+ϕ(v) for every edge {u,v}. A graph is called nice if it contains no isolated edges. As a strengthening of the famous 1-2-3 conjecture, it was conjectured in Wong and Zhu (2011) 23 that every nice graph is total weight (1,3)-choosable. The problem whether there is a constant k such that every nice graph is total weight (1,k)-choosable remained open for a decade and was recently solved by Cao (2021) 6, who proved that every nice graph is total weight (1,17)-choosable. This paper improves this result and proves that every nice graph is total weight (1,5)-choosable.
The hat guessing number of graphs Alon, Noga; Ben-Eliezer, Omri; Shangguan, Chong ...
Journal of combinatorial theory. Series B,
September 2020, 2020-09-00, Letnik:
144
Journal Article
Recenzirano
Odprti dostop
Consider the following hat guessing game: n players are placed on n vertices of a graph, each wearing a hat whose color is arbitrarily chosen from a set of q possible colors. Each player can see the ...hat colors of his neighbors, but not his own hat color. All of the players are asked to guess their own hat colors simultaneously, according to a predetermined guessing strategy and the hat colors they see, where no communication between them is allowed. Given a graph G, its hat guessing number HG(G) is the largest integer q such that there exists a guessing strategy guaranteeing at least one correct guess for any hat assignment of q possible colors.
In 2008, Butler et al. asked whether the hat guessing number of the complete bipartite graph Kn,n is at least some fixed positive (fractional) power of n. We answer this question affirmatively, showing that for sufficiently large n, the complete r-partite graph Kn,…,n satisfies HG(Kn,…,n)=Ω(nr−1r−o(1)). Our guessing strategy is based on a probabilistic construction and other combinatorial ideas, and can be extended to show that HG(C→n,…,n)=Ω(n1r−o(1)), where C→n,…,n is the blow-up of a directed r-cycle, and where for directed graphs each player sees only the hat colors of his outneighbors.
Additionally, we consider related problems like the relation between the hat guessing number and other graph parameters, and the linear hat guessing number, where the players are only allowed to use affine linear guessing strategies. Several nonexistence results are obtained by using well-known combinatorial tools, including the Lovász Local Lemma and the Combinatorial Nullstellensatz. Among other results, it is shown that under certain conditions, the linear hat guessing number of Kn,n is at most 3, exhibiting a huge gap from the Ω(n12−o(1)) (nonlinear) hat guessing number of this graph.
Alternating parity weak sequencing Costa, Simone; Della Fiore, Stefano
Journal of combinatorial designs,
June 2024, Letnik:
32, Številka:
6
Journal Article
Recenzirano
Odprti dostop
A subset S $S$ of a group (G
,
+
) $(G,+)$ is t $t$‐weakly sequenceable if there is an ordering (y
1
,
…
,
y
k
) $({y}_{1},{\rm{\ldots }},{y}_{k})$ of its elements such that the partial sums s
0
,
s
...1
,
…
,
s
k ${s}_{0},{s}_{1},{\rm{\ldots }},{s}_{k}$, given by s
0
=
0 ${s}_{0}=0$ and s
i
=
∑j
=
1
i
y
j ${s}_{i}={\sum }_{j=1}^{i}{y}_{j}$ for 1
≤
i
≤
k $1\le i\le k$, satisfy s
i
≠
s
j ${s}_{i}\ne {s}_{j}$ whenever and 1
≤
∣
i
−
j
∣
≤
t $1\le | i-j| \le t$. By Costa et al., it was proved that if the order of a group is p
e $pe$ then all sufficiently large subsets of the nonidentity elements are t $t$‐weakly sequenceable when p
>
3 $p\gt 3$ is prime, e
≤
3 $e\le 3$ and t
≤
6 $t\le 6$. Inspired by this result, we show that, if G $G$ is the semidirect product of Z
p ${{\mathbb{Z}}}_{p}$ and Z
2 ${{\mathbb{Z}}}_{2}$ and the subset S $S$ is balanced, then S $S$ admits, regardless of its size, an alternating parity t $t$‐weak sequencing whenever p
>
3 $p\gt 3$ is prime and t
≤
8 $t\le 8$. A subset of G $G$ is balanced if it contains the same number of even elements and odd elements and an alternating parity ordering alternates even and odd elements. Then using a hybrid approach that combines both Ramsey theory and the probabilistic method we also prove, for groups G $G$ that are semidirect products of a generic (nonnecessarily abelian) group N $N$ and Z
2 ${{\mathbb{Z}}}_{2}$, that all sufficiently large balanced subsets of the nonidentity elements admit an alternating parity t $t$‐weak sequencing. The same procedure works also for studying the weak sequenceability for generic sufficiently large (not necessarily balanced) sets. Here we have been able to prove that, if the size of a subset S $S$ of a group G $G$ is large enough and if S $S$ does not contain 0, then S $S$ is t $t$‐weakly sequenceable.
Given a simple graph G, a proper total-k-coloring ϕ:V(G)∪E(G)→{1,2,…,k} is called neighbor sum distinguishing if Sϕ(u) ≠ Sϕ(v) for any two adjacent vertices u, v ∈ V(G), where Sϕ(u) is the sum of the ...color of u and the colors of the edges incident with u. It has been conjectured by Pilśniak and Woźniak that Δ(G)+3 colors enable the existence of a neighbor sum distinguishing total coloring. The conjecture is confirmed for any graph with maximum degree at most 3 and for planar graph with maximum degree at least 11. We prove that the conjecture holds for any planar graph G with Δ(G)=10. Moreover, for any planar graph G with Δ(G) ≥ 11, Δ(G)+2 colors guarantee such a total coloring, and the upper bound Δ(G)+2 is tight.
Let G=(V,E) be a graph. A proper total weighting of G is a mapping w:V∪E⟶R such that the following sum for each v∈V:w(v)+∑e∈E(v)w(e) gives a proper vertex colouring of G. For any a,b∈N+, we say that ...G is total weight (a,b)-choosable if for any {Sv:v∈V}⊂Ra and {Se:v∈E}⊂Rb, there exists a proper total weighting w of G such that w(v)∈Sv for v∈V and w(e)∈Se for e∈E. A strengthening of the 1-2-3 Conjecture states that every graph without an isolated edge is total weight (1,3)-choosable. In this paper, we prove that every graph without an isolated edge is total weight (1,17)-choosable. We also prove some new results on the total weight choosability of bipartite graphs.
PDF
