EUVIMEDEUVIMED entdecken
Crossref

A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs

Mingqing Zhai, Huiqiu Lin

Journal of Graph Theory · 2023-03 · 102 (3) · 502-520

DOI: 10.1002/jgt.22883 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 02.09.2022. Verfasst von Mingqing Zhai und 1 weiteren Autor:innen. Die Arbeit wurde bisher 35-mal zitiert (Crossref) und nennt 45 Literaturangaben. Gefördert von: Natural Science Foundation of Shanghai.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A graph is color‐critical if it contains an edge whose removal reduces its chromatic number. Let be the Turán graph with vertices and parts. Given a graph , let be the Turán number of . Simonovits' chromatic critical edge theorem states that if is color‐critical with , then there exists an such that and the Turán graph is the only extremal graph provided . Nikiforov proved a spectral chromatic critical edge theorem. It asserts that if is color‐critical and , then there exists an (which is exponential with ) such that and is the only extremal graph provided , where is the spectral radius of and . In addition, if is either a complete graph or an odd cycle, then is linear with . A book graph is a set of triangles sharing a common edge and a theta graph is a graph which consists of two vertices connected by three internally disjoint paths with length one, two, and . Notice that both and are color‐critical. In this article, we prove that if , then contains a book with unless . Similarly, we prove that if , then contains a theta graph with for odd and for even unless . Our results imply that in the spectral chromatic critical edge theorem is linear with for book graphs and theta graphs. Our result for book graphs can be viewed as a spectral version of an Erdős conjecture (1962) stating that every ‐vertex graph with contains a book graph with Moreover, our result for theta graphs yields that every graph with contains a cycle of length for each . This is related to an open question by Nikiforov (2008) which asks for the maximum such that every graph of large enough order with contains a cycle of length for every .

Förderung

  • Natural Science Foundation of Shanghai

Zitieren

APA

Zhai, M., & Lin, H. (2023). A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs. Journal of Graph Theory, 102(3), 502-520. https://doi.org/10.1002/jgt.22883

Vancouver

Zhai M, Lin H. A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs. Journal of Graph Theory. 2023;102(3):502-520. doi:10.1002/jgt.22883

BibTeX
@article{Zhai2023,
  author = {Zhai, Mingqing and Lin, Huiqiu},
  title = {A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs},
  journal = {Journal of Graph Theory},
  year = {2023},
  volume = {102},
  number = {3},
  pages = {502--520},
  doi = {10.1002/jgt.22883}
}
Kostenlos starten →