Coloring graph classes with no induced fork via perfect divisibility
Coloring graph classes with no induced fork via perfect divisibility
复制标题
通过完美可分性对没有诱导分叉的图类进行着色
DOI：
--
复制
发表时间：
2021
影响因子：
0.7
通讯作者：
Vaidy Sivaraman
中科院分区：
文献类型：
--
作者：
T. Karthick;Jenny Kaufmann;Vaidy Sivaraman
对于图$G$，$\chi(G)$表示它的色数，$\omega(G)$表示它的团数。图$G$称为完全可分的，如果对于$G$的所有导出子图$H$，$V(H)$可以分成两个集合$A$，$B$，使得$H[A]$是完全的，且$\omega(H[B])<；\omega(H)$。一个整数值函数$f$被称为遗传图类$\cal C$的$$\chi$-绑定函数，如果对每个图$G\cal C$都有$\chi(G)\leq f(\omega(G))$.分叉是从完全二部图$K_{1，3}$中细分一次边得到的图。寻找这类无叉图的二次$\chi结合函数的问题是公开的。本文研究了几类无叉图的结构，特别是在完全可除性的背景下，我们研究了一类(Fork，$F$)无叉图，其中$F$是一个有一个稳定集为3的5个顶点的图，并且证明了G$中的每个$G都满足$chi(G)\le omega(G)^2$。我们还注意到，类$\cal G$不允许线性$\chi$绑定函数。
For a graph $G$, $\chi(G)$ will denote its chromatic number, and $\omega(G)$ its clique number. A graph $G$ is said to be perfectly divisible if for all induced subgraphs $H$ of $G$, $V(H)$ can be partitioned into two sets $A$, $B$ such that $H[A]$ is perfect and $\omega(H[B]) < \omega(H)$. An integer-valued function $f$ is called a $\chi$-binding function for a hereditary class of graphs $\cal C$ if $\chi(G) \leq f(\omega(G))$ for every graph $G\in \cal C$. The fork is the graph obtained from the complete bipartite graph $K_{1,3}$ by subdividing an edge once. The problem of finding a quadratic $\chi$-binding function for the class of fork-free graphs is open. In this paper, we study the structure of some classes of fork-free graphs; in particular, we study the class of (fork, $F$)-free graphs $\cal G$ in the context of perfect divisibility, where $F$ is a graph on five vertices with a stable set of size three, and show that every $G\in \cal G$ satisfies $\chi(G)\le \omega(G)^2$. We also note that the class $\cal G$ does not admit a linear $\chi$-binding function.
无诱导叉的无平方图
DOI：
10.37236/9144
发表时间：
2021
期刊：
The Electronic Journal of Combinatorics
影响因子：
--
作者：
Chudnovsky, Maria;Huang, Shenwei;Karthick, T.;Kaufmann, Jenny
通讯作者：
Kaufmann, Jenny
不包括分叉和反分叉
影响因子：
0.8
作者：
Chudnovsky, Maria;Cook, Linda;Seymour, Paul
通讯作者：
Seymour, Paul