惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

G
Google Developers Blog
酷 壳 – CoolShell
酷 壳 – CoolShell
量子位
C
Check Point Blog
B
Blog RSS Feed
Y
Y Combinator Blog
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
A
About on SuperTechFans
Microsoft Azure Blog
Microsoft Azure Blog
博客园 - 聂微东
阮一峰的网络日志
阮一峰的网络日志
人人都是产品经理
人人都是产品经理
小众软件
小众软件
Last Week in AI
Last Week in AI
博客园 - 【当耐特】
GbyAI
GbyAI
The Cloudflare Blog
博客园 - 叶小钗
S
SegmentFault 最新的问题
博客园 - Franky
Engineering at Meta
Engineering at Meta
F
Fortinet All Blogs
B
Blog
Jina AI
Jina AI

math updates on arXiv.org

Coupling-Robust Accuracy in Multiphysics Physics Informed Neural Networks via Kronecker-Preconditioned Optimization Non-normal spectral signatures of instability in neural network training dynamics Optimization of randomized neural networks for transfer operator approximation Selective Ambulance Dispatch Under Contextual Travel-Time Uncertainty LLAMA LIMA: A Living Meta-Analysis on the Effects of Generative AI on Learning Mathematics Neural Flow Operators can Approximate any Operator: Abstract Frameworks and Universal Approximations LLMs as Noisy Channels: A Shannon Perspective on Model Capacity and Scaling Laws On the Stability of Spherical Hellinger-Kantorovich Flows and Their Implications for Differential Privacy Training-Free Looped Transformers Move on Muon : A Hamiltonian probability gradient flow perspective of Muon optimizer Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries Asymmetric Scaling Laws from Sparse Features Is Dimensionality a Barrier for Retrieval Models? RA-DCA: A Randomized Active-Set DCA for Directional Stationarity in Max-Structured DC Programs Commutator-Induced Uncertainty in VAEs Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them Sparse In-Network Learning via Shortest-Path Backpropagation and Finite-Rate Gating Instance-Optimal Estimation with Multiple LLM Judges on a Budget Entropy Equivalence Testing Expand More, Shrink Less: Shaping Effective-Rank Dynamics for Dense Scaling in Recommendation Any-Dimensional Invariant Universality Operationalizing Individual Fairness via Gradient Descent and Bradley-Terry Models Anytime Training with Schedule-Free Spectral Optimization Diffusion-based Denoising Beats Vanilla Score Matching in Parameter Estimation: A Theoretical Explanation Resilience Characterization of AI-Native Wireless Receivers via Persistent Homology The General Theory of Localization Methods Group-Algebraic Tensors: Provably-optimal Equivariant Learning and Physical Symmetry Discovery General Lower Bounds for Differentially Private Federated Learning with Arbitrary Public-Transcript Interactions PilotWiMAE: Pilot-Native Representation Learning for Wireless Channels Proximal basin hopping: global optimization with guarantees
A Domatic Analogue of $χ$-Bounded Graph Classes and the G...
Quentin Chuet, Selma Djelloul, Hoang La, François Pirot, Hossein · 2026-06-01 · via math updates on arXiv.org

Given a graph $G$, a dominating set is a subset $X\subseteq V(G)$ such that $N[X]=V(G)$. The \emph{domatic number} of $G$, denoted ${\rm dom}(G)$, is the maximum size of a partition of $V(G)$ into dominating sets. In analogy with the lower bound of the chromatic number by the clique number, the domatic number satisfies the upper bound ${\rm dom}(G)\le δ(G)+1$ where $δ(G)$ is the minimum degree of $G$. Therefore, as an analogue of the notion of $χ$-bounded graph classes, we say that a class of graphs $\mathscr{G}$ is \emph{DOM-bounded} if there exists a positive unbounded function $f_{\mathscr{G}}$ such that for every $G\in \mathscr{G}$, we have ${\rm dom}(G) \ge f_{\mathscr{G}}(δ(G))$. We propose the following conjecture for graphs forbidding a fixed induced subgraph, analogous to the Gyárfás--Sumner Conjecture for $χ$-bounded graph classes: for every connected graph $H$, the class of $H$-free graphs is DOM-bounded if and only if $H$ is a tree of diameter at most $3$. We reduce the case of disconnected graphs to the connected setting and show that the conditions on $H$ are necessary. We show that star-free graphs of minimum degree at least $δ$ have domatic number $Ω(δ/\log δ)$, which is best possible up to a constant factor. We also identify a subclass of star-free graphs for which the domatic number is linear in $δ$: line graphs of bounded rank hypergraphs. In support of our conjecture in the case of double stars, we prove that $P_4$-free graphs (i.e. cographs) of minimum degree $δ$ have domatic number at least $1 + \fracδ{2}$, which is best possible.