What type of study is this?

This is a Quantitative Study study.

October 13, 2025Open Access

How to find all extremal graphs using symmetric subgraphs

Key Points

Characterizing all extremal graphs involves examining their symmetrical properties and chromatic characteristics.
New extremal results expand existing knowledge on graph families with specific subgraph restrictions.
The research utilizes the Turán graph concept to define graph structures with maximum edges.
The study aims to enhance graph theory by linking symmetry in graphs to chromatic constraints.

Abstract

Let F be a finite family of graphs with ₅ ₅χ (F) =r+13, where χ (F) is the chromatic number of F. Set t=₅|F|. Let EX (n, F) be the set of graphs with maximum edges among all the graphs of order n without any F as a subgraph. Let T (n, r) be the Turán graph of order n with r parts. Assume that some F₀ is a subgraph of the graph obtained from T (rt, r) by embedding a path in its one part. Simonovits S1 introduced the concept of symmetric subgraphs, and proved that there exist graphs in EX (n, F) which have symmetrical property. In this paper, we aim to find a way to characterize all the extremal graphs for such F using symmetric subgraphs. Some new extremal results are obtained.

Read Full Paperexternally

Bookmark

View Full Paper

Cite This Study

Wenqian Zhang (Tue,) studied this question.

synapsesocial.com/papers/68ed1896f29694dd1da78bef https://doi.org/https://doi.org/10.48550/arxiv.2509.07954