We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Enhancing the Erdős‐Lovász Tihany Conjecture for line graphs of multigraphs.
- Authors
Wang, Yue; Yu, Gexin
- Abstract
In this paper, we prove an enhanced version of the Erdős‐Lovász Tihany Conjecture for line graphs of multigraphs. That is, for every line graph G $G$ whose chromatic number χ(G) $\chi (G)$ is more than its clique number ω(G) $\omega (G)$ and for any nonnegative integer ℓ $\ell $, any two integers s,t≥3.5ℓ+2 $s,t\ge 3.5\ell +2$ with s+t=χ(G)+1 $s+t=\chi (G)+1$, there is a partition (S,T) $(S,T)$ of the vertex set V(G) $V(G)$ such that χ(G[S])≥s $\chi (G[S])\ge s$ and χ(G[T])≥t+ℓ $\chi (G[T])\ge t+\ell $. In particular, when ℓ=1 $\ell =1$, we can obtain the same result just for any s,t≥4 $s,t\ge 4$. The Erdős‐Lovász Tihany conjecture for line graphs is a special case when ℓ=0 $\ell =0$.
- Subjects
LOGICAL prediction; INTEGERS; CHROMATIC polynomial; MULTIGRAPH; PARTITIONS (Mathematics)
- Publication
Journal of Graph Theory, 2022, Vol 101, Issue 1, p134
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.22816