pith. machine review for the scientific record. sign in

arxiv: 1805.11437 · v1 · submitted 2018-05-27 · 🧮 math.CO

Recognition: unknown

ErdH{o}s-Lov\'asz Tihany Conjecture for graphs with forbidden holes

Authors on Pith no claims yet
classification 🧮 math.CO
keywords graphconjecturegraphsalphas-lovsplittabletihanyevery
0
0 comments X
read the original abstract

A hole in a graph is an induced cycle of length at least $4$. Let $s\ge2$ and $t\ge2$ be integers. A graph $G$ is $(s,t)$-splittable if $V(G)$ can be partitioned into two sets $S$ and $T$ such that $\chi(G[S ]) \ge s$ and $\chi(G[T ]) \ge t$. The well-known Erd\H{o}s-Lov\'asz Tihany Conjecture from 1968 states that every graph $G$ with $\omega(G) < \chi(G) = s + t - 1$ is $(s,t)$-splittable. This conjecture is hard, and few related results are known. However, it has been verified to be true for line graphs, quasi-line graphs, and graphs with independence number $2$. In this paper, we establish more evidence for the Erd\H{o}s-Lov\'asz Tihany Conjecture by showing that every graph $G$ with $\alpha(G)\ge3$, $\omega(G) < \chi(G) = s + t - 1$, and no hole of length between $4$ and $2\alpha(G)-1$ is $(s,t)$-splittable, where $\alpha(G)$ denotes the independence number of a graph $G$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.