Coloring Graphs With No Totally Odd Clique Immersion

McFarland, Caleb

数学 > 组合数学

arXiv:2508.08119v2 (math)

[提交于 2025年8月11日 (v1) ，最后修订 2025年8月19日 (此版本， v2)]

标题：不含完全奇团浸入的图着色

标题： Coloring Graphs With No Totally Odd Clique Immersion

Authors:Caleb McFarland

摘要：我们证明了不包含$K_t$的完全奇数浸入的图是$\mathcal{O}(t)$-可着色的。特别地，我们表明任何不包含$K_t$的完全奇数浸入的图都是一个二分图和一个禁止浸入$K_{\mathcal{O}(t)}$的图的并集。我们的结果具有算法性，并给出了一个固定参数可tractable算法（在$t$中）来找到这样的分解。

摘要： We prove that graphs that do not contain a totally odd immersion of $K_t$ are $\mathcal{O}(t)$-colorable. In particular, we show that any graph with no totally odd immersion of $K_t$ is the union of a bipartite graph and a graph which forbids an immersion of $K_{\mathcal{O}(t)}$. Our results are algorithmic, and we give a fixed-parameter tractable algorithm (in $t$) to find such a decomposition.

主题：	组合数学 (math.CO) ; 离散数学 (cs.DM)
MSC 类：	05C15, 05C83
ACM 类：	G.2.2
引用方式：	arXiv:2508.08119 [math.CO]
	(或者 arXiv:2508.08119v2 [math.CO] 对于此版本)
	https://doi.org/10.48550/arXiv.2508.08119

提交历史

来自： Caleb McFarland [查看电子邮件]
[v1] 星期一， 2025 年 8 月 11 日 15:57:58 UTC (22 KB)
[v2] 星期二， 2025 年 8 月 19 日 21:00:41 UTC (22 KB)

数学 > 组合数学

标题：不含完全奇团浸入的图着色

标题： Coloring Graphs With No Totally Odd Clique Immersion

提交历史

获取论文：

参考文献与引用

收藏

文献和引用工具

与本文相关的代码，数据和媒体

演示

推荐器和搜索工具

arXivLabs：与社区合作伙伴的实验项目

数学 > 组合数学

标题： 不含完全奇团浸入的图着色 显示英文标题

标题： Coloring Graphs With No Totally Odd Clique Immersion

提交历史

获取论文：

参考文献与引用

BibTeX 格式的引用

收藏

文献和引用工具

与本文相关的代码，数据和媒体

演示

推荐器和搜索工具

arXivLabs：与社区合作伙伴的实验项目

标题：不含完全奇团浸入的图着色