1. Partition line graphs of multigraphs into two subgraphs with large chromatic numbers.
- Author
-
Lv, Jian-Bo and Li, Jianxi
- Subjects
- *
SUBGRAPHS , *MULTIGRAPH , *INTEGERS , *LOGICAL prediction - Abstract
Wang and Yu (2022) prove an enhanced version of the Erdős–Lovász Tihany conjecture for line graphs of multigraphs. That is, let s , t and ℓ be arbitrary integers with t ≥ s ≥ 3. 5 ℓ + 2 , ℓ ≥ 0. If the line graph L (G) of some multigraph G has chromatic number s + t − 1 > ω (L (G)) , then there is a partition (S , T) of the vertex set V (L (G)) such that χ (L (G) [ S ]) ≥ s and χ (L (G) [ T ]) ≥ t + ℓ. In this paper, for integers s and t with t ≥ s ≥ 7 , we prove that for each line graph L (G) with χ (L (G)) = s + t − 1 ≥ ω (L (G)) , there is a partition (S , T) of the vertex set V (L (G)) such that χ (L (G) [ S ]) ≥ s and χ (L (G) [ T ]) ≥ t + 2 , which slightly improves the recent result of Wang and Yu (2022) for ℓ = 2. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF