EUVIMEDEUVIMED entdecken
Crossref

The independence number and chromatic number in a reduced graph

Meng Zhang

Congressus Numerantium · 2025

DOI: 10.61091/cn236-04 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Congressus Numerantium, 2025. Verfasst von Meng Zhang.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →