论文库

We study upper bounds for the triameter of a connected graph in terms of distance packings and vertex connectivity. For any positive integer $k$, we bound the triameter of a graph by a linear function of its $k$-packing number and show that this bound is tight for all values of the parameters. As a corollary, we confirm the conjecture of Das and Abdioğlu on the upper bound for the triameter in terms of the order and the minimum degree of a graph. We also find the maximum triameter among graphs with given order and vertex connectivity, and describe the extremal graphs. Our main tool is a projection of a graph onto a spider or a unicyclic graph which preserves the distances between three prescribed vertices.

For a graph $G=(V,E)$, the boxicity $\operatorname{box}(G)$ is the least integer $d$ such that $G$ is the intersection graph of axis-parallel boxes in $\mathbb{R}^d$. The Kneser graph $K(n,k)$ is the graph whose vertex set corresponds to the family of $k$ sized subsets of an $n$ sized ground set, and a pair of vertices are adjacent if and only if the corresponding sets are disjoint. In this short paper, we provide new bounds for the boxicity of $K(n,k)$. We first show that for $k\ge 2$ and $n\ge 2k+1$, $\operatorname{box}(K(n,k))\ge n-2k$, thereby improving the lower bounds of Caoduro and Lichev [Discrete Mathematics 346(5):113333 (2023)] when $n\geq 3k+1$ and $k\ge 3$. The proof of this result uses the topological method and follows a strategy similar to Greene's proof of the Kneser's conjecture on the chromatic number of $K(n,k)$. We also show that for $k\ge 2$, $t\ge 1$ and $n=2k+t$, $\operatorname{box}(K(2k+t,k)) \leq O( t^3\log(2k+t) ).$ In particular, for every $t=t(k)\ge1$ with $t^3\log k=o(k)$, $\operatorname{box}(K(2k+t,k))=o(k)$. This is the first upper bound on the boxicity of $K(n,k)$ that is sublinear in $n$. We also show that for large enough $k$, $\operatorname{box}(K(2k+1,k))\le \frac{3\ln (2k+1)}{\ln\ln (2k+1)}$.

A digraph consisting of a set of vertices $V$ and a set of arcs $E$ is called an interval digraph if there exists a family of closed intervals $\{I_u,J_u\}_{u \in V}$ such that $uv$ is an arc if and only if the intersection of $I_u$ and $J_v$ is non-empty. Interval digraphs naturally generalize interval graphs, by extending the classical interval intersection model to directed graphs. Several subclasses of interval digraphs have been studied in the literature-such as balanced, chronological and catch interval digraphs-each characterized by admitting interval representations that satisfy specific restrictions. Among these, interval nest digraphs are the ones that admit an interval representation in which $J_u$ is contained in $I_u$ for all vertices $u$ of $V$. In this work, we provide a complete characterization of interval nest digraphs in terms of vertex linear orderings with forbidden patterns, which we call nest orderings. This result completes the picture of vertex-ordering characterizations among the main subclasses of interval digraphs.

A zero-forcing set of a graph is a set for which, after regarding each of its vertices as being blue, and applying the rule that a blue vertex with exactly one white neighbor forces said neighbor to become blue, all of the vertices in the graph are blue. Let $z(G;k)$ denote the number of zero forcing sets of size $k$. A conjecture of Boyer et al.\ asserts that the path $P_n$ maximizes these numbers coefficientwise among all $n$-vertex graphs. We prove this path-extremal conjecture for distance-hereditary graphs, which is the class of all graphs $G$ such that for each of the connected induced subgraphs of $G$, the distances between any two vertices in that subgraph are the same as they are in $G$. This extends the previously known tree case in which the path-extremal conjecture was known to be true to a much larger class that includes, in particular, all trees and all cographs. We then use canonical split decomposition to push the argument we used to show the distance-hereditary result into the more general setting of a connected graph with at most one prime bag in its canonical split decomposition. Specifically, we show that if a split-prime graph $H$ and all of its induced subgraphs are path-extremal, then every connected graph whose canonical split decomposition has a unique prime bag whose label graph is isomorphic to $H$ is also path-extremal. As a corollary of this result, for each fixed $m$, if every induced subgraph of every split-prime graph on at most $m$ vertices is path-extremal, then so is every connected graph whose canonical split decomposition has a unique prime bag of size at most $m$. Additionally, we prove that the path-extremal conjecture holds when all prime bags have order at most six, without restricting their number; under the preceding hereditary hypothesis, one additional prime bag labelled by $H$ is also allowed.

We study online coloring, focusing on the competitive ratio. The best previously known results were (1) a lower bound of $Ω(n / \log^2 n)$ for both deterministic and randomized algorithms by Halldórsson and Szegedy (1994), (2) an upper bound of $O(n / \log n)$ for randomized algorithms by Halldórsson (1997), and (3) an upper bound of $O(n / \log \log n)$ for deterministic algorithms by Kawarabayashi, Yoneda, and Yoneda (2025). In this paper, we improve these results as follows: 1. A new lower bound of $Ω(n / \log n)$ for deterministic algorithms. 2. A new upper bound of $O(n (\log \log n)^2 / \log^2 n)$ for randomized algorithms. 3. A new upper bound of $O(n / (\log \log n)^{2-\varepsilon})$ for deterministic algorithms for every fixed $\varepsilon>0$. For randomized algorithms, we nearly close the gap between the lower and upper bounds; the remaining gap is only $O((\log \log n)^2)$. We establish the asymptotic separation between randomized and deterministic online graph coloring. Against an oblivious adversary, a polynomial-time randomized algorithm achieves a competitive ratio asymptotically smaller than any deterministic algorithm can guarantee, even with unlimited computation.

The Path Avoiding Forbidden Pairs problem (PAFP) asks whether, in a directed graph $G$ with two of its vertices labeled $s,t$ and a set $\mathcal F$ of forbidden vertex pairs, there is an $s$--$t$ path that contains at most one endpoint from each pair in $\mathcal F$. We initiate the study of PAFP through a layer-based width measure. We first look at the directed union digraph $G\cup\mathcal F$, which is obtained by adding one arc per forbidden pair to $G$, oriented according to a fixed reachability-compatible order. Let the BFS layer $L_d$ be the set of vertices at directed shortest-path distance $d$ from $s$, and define the BFS-width from $s$ as $\max_d |L_d|$. We show that if $G\cup\mathcal F$ has BFS-width $b$ from $s$, and $p$ is the maximum, over BFS-layer cuts, of the smaller of the numbers of distinct heads and distinct tails of backward arcs crossing the cut, then PAFP is FPT parameterized by $b+p$. Here a backward arc goes from a later BFS layer to an earlier one. In contrast, we show that bounded BFS-width alone does not suffice: PAFP remains $\mathsf{NP}$-complete when the union digraph has BFS-width 2. We also study layer-based width parameters on the input graph. We show that if the input DAG has BFS-width at most $2$ and only $k$ backward input arcs, then PAFP can be decided in $2^k |I|^{O(1)}$ time, with unrestricted forbidden pairs, and this result is tight. Moreover, we study exact-length layers in the input graph, where the $d$-th exact-length layer consists of the vertices reachable from $s$ by a directed path of length exactly $d$. We show that for DAGs of exact-length width at most $2$, PAFP is polynomial-time decidable by a $2$-SAT encoding of fixed-length paths. Unlike previously known polynomial-time regimes our 2 input -graph tractability results simultaneously allow unrestricted forbidden pairs and input graphs with exponentially many $s$--$t$ paths.

We show that, given a Horn expression and a family of inclusion-wise maximal satisfiable subsets of its clauses, deciding whether there exists another maximal satisfiable subset is NP-complete. As a consequence, unless P=NP, there is no output-polynomial time algorithm enumerating the maximal satisfiable subformulas of a Horn expression.

A foundational theorem of Ajtai, Komlós, Pintz, Spencer, and Szemerédi asserts that every $n$-vertex $k$-uniform uncrowded hypergraph (i.e., with girth at least $5$) of maximum degree at most $Δ$ contains an independent set of size $cn(\logΔ/Δ)^{\frac{1}{k-1}}$ for some absolute constant $c>0$. Improving an earlier bound of Frieze and Mubayi, Iliopoulos showed that every such hypergraph has list chromatic number at most $(1+o(1))(k-1)(Δ/\logΔ)^{\frac{1}{k-1}}$. Determining the optimal leading constant in this bound remains a major open problem. A natural target, suggested by the coupon-collector heuristic, is $(k-1)^{\frac{1}{k-1}}$, which also corresponds to the shattering threshold for coloring sparse random hypergraphs. Our main result shows that this target is attained: for every integer $k\ge2$, every $k$-uniform uncrowded hypergraph of maximum degree at most $Δ$ satisfies: $$χ_\ell(\mathcal{H})\le(1+o(1))\Big((k-1)\fracΔ{\logΔ}\Big)^{\frac{1}{k-1}}.$$ In particular, this confirms a 2019 conjecture of Molloy for uncrowded hypergraphs. Building on this result, we prove that every $k$-uniform linear hypergraph of maximum degree at most $Δ$ has chromatic number at most $(c_k+o(1))(Δ/\logΔ)^{\frac{1}{k-1}}$, where $c_k\to1$ as $k\to\infty$, thereby proving a conjecture of Verstraëte and Wilson on the independence number of linear hypergraphs in the stronger form of colorings. Our techniques also yield a palette sparsification theorem for uncrowded hypergraphs, partially answering a question of Casselgren and Eriksson.

The nonnegative rank of a nonnegative matrix $X$ is the smallest number of nonnegative rank-one factors that sum to $X$. Since computing the nonnegative rank is NP-hard, it is common to circumvent this issue by computing lower and upper bounds. In this paper, we propose non-convex formulations and practical implementations for four important lower bounds for the nonnegative rank, namely the fooling set bound (FSB), the rectangle covering bound (RCB), the hyperplane separation bound (HSB), and the self-scaled bound (SSB). In particular, to the best of our knowledge, our algorithm for computing the SSB is the first available in the literature. We compute the SSB for several matrices for which its value had not previously been reported. In some cases, the SSB provides the best known upper bound, while the other three bounds do not. Moreover, on canonical benchmarks, we show that our non-convex approaches are often competitive with existing methods. The paper also provides a consolidated reference for the current state of several classical lower bounds on a large number of benchmark matrices.