The independence number and chromatic number in a reduced graph
Congressus Numerantium · 2025
DOI: 10.61091/cn236-04 ↗Kurz gefasst
Fachartikel in der Zeitschrift Congressus Numerantium, 2025. Verfasst von Meng Zhang.
Abstract (Originalsprache)
Let G be a loopless connected graph. A graph G is reduced if it contains no collapsible subgraph. Catlin (posted by Chen and Lai [9]) conjectured that every connected reduced graph is either 2-colorable or 3-colorable. A weaker conjecture states that the independence number of a connected reduced graph G is at least one-third of its number of vertices. In this paper, we establish a lower bound on the independence number in reduced graphs. As an application, we examine the independence number conjecture for reduced graphs with a given upper bound on the number of vertices. Also, we investigate the chromatic number of reduced planar graphs under given conditions.
Zitieren
APA
Zhang, M. (2025). The independence number and chromatic number in a reduced graph. Congressus Numerantium. https://doi.org/10.61091/cn236-04
Vancouver
Zhang M. The independence number and chromatic number in a reduced graph. Congressus Numerantium. 2025. doi:10.61091/cn236-04
BibTeX
@article{Zhang2025,
author = {Zhang, Meng},
title = {The independence number and chromatic number in a reduced graph},
journal = {Congressus Numerantium},
year = {2025},
doi = {10.61091/cn236-04}
}
EUVIMED