pith. sign in

arxiv: 1309.1020 · v1 · pith:XM5KYQWKnew · submitted 2013-09-04 · 🧮 math.CO

On the Erd\"os-Lov\'asz Tihany Conjecture for Claw-Free Graphs

classification 🧮 math.CO
keywords graphsconjecturecitequasi-lineclaw-freelinecasesclasses
0
0 comments X
read the original abstract

In 1968, Erd\"os and Lov\'asz conjectured that for every graph $G$ and all integers $s,t\geq 2$ such that $s+t-1=\chi(G) > \omega(G)$, there exists a partition $(S,T)$ of the vertex set of $G$ such that $\chi(G|S)\geq s$ and $\chi(G|T)\geq t$. For general graphs, the only settled cases of the conjecture are when $s$ and $t$ are small. Recently, the conjecture was proved for a few special classes of graphs: graphs with stability number 2 \cite{quasi-line}, line graphs \cite{line} and quasi-line graphs \cite{quasi-line}. In this paper, we consider the conjecture for claw-free graphs and present some progress on it.

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.