Rainbow subgraphs of star-coloured graphs

Basic Information

• Paper ID: 2511.12505
• Title: Rainbow subgraphs of star-coloured graphs
• Authors: Allan Lo, Klas Markström, Dhruv Mubayi, Katherine Staden, Maya Stein, Lea Weber
• Classification: math.CO (Combinatorics)
• Publication Date: November 18, 2025
• Paper Link: https://arxiv.org/abs/2511.12505

Abstract

This paper investigates the rainbow subgraph problem in star-coloured graphs. An edge coloring loses the rainbow property for two reasons: either it contains a monochromatic cherry (a pair of adjacent edges) or a monochromatic matching of size 2. Proper coloring forbids the first structure, while star coloring forbids the second. The paper determines the maximum number of colors in a star coloring of a large complete graph that does not contain a rainbow copy of a given graph H. This is a special case of the generalized Ramsey number problem studied by Axenovich and Iverson, and the paper extends their results.

Research Background and Motivation

1. Research Problem

The paper studies the star anti-Ramsey number ar⋆(n,H), defined as the maximum number of colors in a star coloring of the complete graph Kₙ that does not contain a rainbow copy of graph H.

2. Problem Significance

• Theoretical Importance: Anti-Ramsey theory is a central problem in extremal graph theory, studying the maximum number of colors needed to avoid specific structures under given coloring constraints
• Generalization of Classical Problems: The classical anti-Ramsey number ar(n,H) (introduced by Erdős et al. in 1975) studies arbitrary edge colorings; this paper studies the more restricted case of star colorings
• Interdisciplinary Connections: Links multiple branches of combinatorial mathematics including graph coloring, extremal graph theory, and vertex arboricity

3. Limitations of Existing Research

• Axenovich and Iverson (2008) proved that when va(H) ≥ 3, ar⋆(n,H) = (1+o(1))(1-1/(va(H)-1))(n choose 2)
• However, when vertex arboricity va(H) ≤ 2, only crude upper bounds ar⋆(n,H) ≤ n^(2-1/c) are known
• Exact values for specific graphs (such as cycles, complete graphs, and graph joins) are largely unknown

4. Research Motivation

This paper aims to fill the gap in the va(H) = 2 case by determining exact or asymptotic values of the star anti-Ramsey number for various important graph classes.

Core Contributions

The main contributions of this paper include:

1. Exact Results for Cycles (Theorem 1.4): For all k ≥ 3, prove ar⋆(n,Cₖ) = n + (k-2 choose 2) - 1, and completely characterize the structure of extremal colorings
2. Exact Value for K₄ (Theorem 1.5): Prove ar⋆(n,K₄) = 2n - 3, which is the technically most complex result
3. Exact Results for K₄⁻ (Theorem 1.6): Prove ar⋆(n,K₄⁻) = ⌊3(n-1)/2⌋ and characterize all extremal colorings
4. Asymptotic Bounds for K₅⁻ (Theorem 1.7): Prove (1+o(1))(n choose 2)^(3/2) ≤ ar⋆(n,K₅⁻) ≤ (1+o(1))16(n choose 2)^(3/2)
5. General Results for Tree Joins (Theorem 1.8): For trees T₁, T₂ on s,t ≥ 3 vertices, prove ex(n,Kₛ,ₜ⁻)/2 ≤ ar⋆(n,T₁+T₂) ≤ cn^(2-1/s)
6. Realization of Extremal Densities (Corollary 1.10): Prove that for each integer s ≥ 1, the density 2-1/s is star-realizable

Methodology Details

Task Definition

Star Coloring: An edge coloring of the complete graph Kₙ such that each color class induces a star (or triangle, but this case is excluded in the paper)

Star Anti-Ramsey Number: ar⋆(n,H) := max{s ∈ ℕ : there exists an s-colored star coloring of Kₙ containing no rainbow copy of H}

Key Concepts:

• Vertex arboricity va(H): minimum number of parts into which vertices can be partitioned such that each part induces a forest
• Edge arboricity ea(H): minimum number of parts into which edges can be partitioned such that each part induces a forest
• Relationship: va(H) ≤ ea(H) ≤ ⌈e(H)/(v(H)-1)⌉

Core Technical Framework

The paper employs multiple technical tools:

1. Special Coloring Constructions (Lower Bounds)

Lexical Coloring Gₗₑₓⁿ:

• Take a transitive tournament; the i-th star has center vᵢ and leaves all vⱼ (j > i)
• Number of colors: n-1
• Property: contains no rainbow cycles (Lemma 3.2)

Orientable Coloring G^T_n:

• Given a tournament T, the i-th star has center vᵢ
• Number of colors: n - |{v : d⁺(v)=0}| ∈ {n-1, n}

Rainbow Blow-up Coloring Rₙ(Gₙ₁,...,Gₙₗ):

• Use rainbow coloring on Turán graph Tₗ(n)
• Use given colorings within each part
• Number of colors: tₗ(n) + Σ|C(Gₙᵢ)|

Modified Coloring G(S):

• Start from coloring G and use a new color for each star in an edge-disjoint collection S
• Used to construct sparse rainbow subgraphs

2. Upper Bound Techniques

Oriented Graph Analysis:

• Induce an oriented graph from star coloring: edges point from star centers to leaves
• Utilize properties of tournaments (e.g., Rédei's theorem: every tournament has a directed Hamiltonian path)

Auxiliary Oriented Graphs:

• Construct auxiliary directed graphs capturing coloring structure
• For example, in the K₄ proof, define arc u→v when u is the center of exactly one star

Dependent Random Choice (Lemma 2.2):

• For oriented graph G, if e(G) ≥ cn^(2-1/s), then there exists a set A of size a such that every s-subset of A has ≥ b common out-neighbors
• Used for upper bounds in tree join proofs

Proof Strategies for Main Theorems

Theorem 1.4 (Cycles) Proof Outline:

1. Lower Bound: Construct modified orientable coloring
   • Take Cₖ-free tournament T on n-k+1 vertices
   • Add a clique of k-1 vertices with all edges from T pointing to the clique
   • Rainbow coloring within the clique
2. Upper Bound: Induction
   • If every vertex is the center of ≥2 stars, then there exists a rainbow Cₙ (Lemma 4.3)
   • Otherwise, there exists vertex v that is the center of ≤1 star
   • Apply induction to G-v to obtain structural description

Theorem 1.5 (K₄) Proof Outline (Most Complex):

Employs fine structural analysis:

1. Good Tuples P = (W,Y,Z,x,v*,cZ):
   • Vertex set decompositions satisfying seven properties P1-P7
   • Key: C(Y∪Z) = C(Y) ∪ C(Z) ∪ {cZ}
2. Three-Step Construction:
   • Lemma 6.1: If ⊛(x) ≥ 3, construct great tuple
   • Lemma 6.2: Improve great tuple to restricted tuple
   • Lemma 6.3: Improve restricted tuple to good tuple satisfying C(G) = Cₚ
3. Inductive Completion:
   • |C(G)| ≤ |C(W)| + |C(Y)| + |C(Z)| + 1
   • Recursively apply inductive hypothesis to W,Y,Z

Theorem 1.6 (K₄⁻) Proof Outline:

1. Lower Bound: Modify lexical coloring
   • Base: lexical coloring (n-1 colors)
   • Add ⌊(n-1)/2⌋ edge-disjoint rainbow edges
2. Upper Bound: Induction + structural analysis
   • Analyze matching M: induced subgraph of uniquely colored edges
   • M is at most a matching plus one 2-edge path or triangle
   • Prove e(M) ≥ ⌈n/2⌉

Theorem 1.8 (Tree Joins) Proof Outline:

1. Upper Bound: Dependent random choice
   • Orient each star from its center
   • Find a set A of nar⋆(T₁) vertices such that every s-subset has ≥nar⋆(T₂)+s-1 common out-neighbors
   • Embed T₁ in A and T₂ in common out-neighbors
2. Lower Bound: Modify lexical coloring
   • Key Lemma 7.2: T₁+T₂ minus any forest F contains either an odd cycle or Kₛ,ₜ⁻
   • Utilize ex(n,Kₛ,ₜ⁻) ≥ Ω(n^(2-1/s))

Experimental Setup

This is a pure theoretical mathematics paper with no experiments. All results are obtained through rigorous mathematical proofs.

Main Tools

1. Classical Results in Extremal Graph Theory:
   • Kővári-Sós-Turán theorem
   • Erdős-Stone theorem
   • Known bounds for Zarankiewicz problem
2. Combinatorial Structures:
   • Tournament theory
   • Turán graphs
   • Graph joins
3. Probabilistic Methods:
   • Dependent random choice
   • Chernoff bounds

Experimental Results

Summary of Main Results

Structural Characterizations

Extremal Colorings for Theorem 1.4 (Cycles):

• Vertex sets A, B of sizes n-k+1 and k-1 exist
• Orientation derived from Cₖ-free tournament T on A
• All edges from A to B point from A to B
• Rainbow coloring within B

Extremal Colorings for Theorem 1.6 (K₄⁻):

• Odd n: vertex ordering v₁,...,vₙ, edge vᵢvⱼ colored with min{i,j}, plus ⌊n/2⌋ rainbow edges
• Even n: similar with special structure on 3 vertices

Key Findings

1. ar(n,H) and ar⋆(n,H) can differ significantly:
   • ar(n,K₄) = ex(n,K₃) + 1 = Θ(n²)
   • ar⋆(n,K₄) = 2n - 3 = Θ(n)
2. Realization of Extremal Densities:
   • Proves that 2-1/s is star-realizable for all s≥1
   • Raises Question 1.9: which r∈1,2 are star-realizable?
3. Complex Behavior for Graphs with ea(H)=2:
   • When ea(H)≥3, ar⋆(n,H) is superlinear
   • When ea(H)=2, may be linear (conjecture)

Related Work

1. Anti-Ramsey Theory

Classical Anti-Ramsey Numbers ar(n,H) (Erdős-Simonovits-Sós, 1975):

• ar(n,Cₖ) = (k-2 choose 2) + n/(k-1) + O(1)
• ar(n,Kₖ) = ex(n,Kₖ₋₁) + 1
• General bounds: ex(n,FH⁻) + 1 ≤ ar(n,H) ≤ ex(n,H)

2. Rainbow Subgraphs in Proper Colorings

• Maamoun-Meyniel (1989): Existence of proper coloring of Kₙ with no rainbow Hamiltonian path
• Andersen (1989): Conjecture guaranteeing rainbow paths of length n-2
• Alon-Pokrovskiy-Sudakov (2017): Prove existence of rainbow paths of length n-o(n)

3. Generalized Ramsey Numbers

Axenovich-Iverson (2008):

• Study Rₓ(n,H): maximum colors avoiding monochromatic F and rainbow H
• Prove asymptotic values determined by va(H) when F is not a star
• This paper's result: ar⋆(n,H) = R_{M₂,K₃}(n,{H})

4. Extremal Graph Theory

• Erdős-Stone theorem: ex(n,H) = (1-1/(χ(H)-1)+o(1))(n choose 2) when χ(H)≥3
• Zarankiewicz problem: bounds on z(m,n;s,t)
• Turán density: which r∈1,2 are extremal-realizable

Conclusions and Discussion

Main Conclusions

1. Complete Resolution of Multiple Important Cases with va(H)=2:
   • Cycles: exact values and structural characterization
   • Small complete graphs: exact values for K₃, K₄, K₄⁻
   • Tree joins: asymptotic orders
2. Establishment of New Technical Framework:
   • Good tuple method for handling complex structures
   • Modified coloring constructions for lower bounds
   • Dependent random choice for upper bounds
3. Connections Across Multiple Mathematical Fields:
   • Star coloring and vertex arboricity
   • Extremal graph theory and Ramsey theory
   • Tournament theory

Limitations

1. Extremal Colorings for K₄⁻ and Larger Graphs Not Completely Characterized:
   • K₄ has multiple extremal colorings; paper does not provide complete classification
   • Exact values for K₅ and larger complete graphs remain unknown
2. General Theory for ea(H)=2 Incomplete:
   • Conjecture ar⋆(n,H) = Θ(n) when ea(H)=2, but unproven
   • Behavior of 4-regular graphs unclear
3. Gaps in Tree Join Bounds:
   • Upper and lower bounds differ by constant factors
   • Exact constants undetermined
4. Set of Star-Realizable Densities Not Completely Determined:
   • Only proves realizability of 2-1/s
   • Question 1.9: which r∈1,2 are star-realizable?

Future Directions

The paper proposes multiple open problems in Section 8:

Question 8.1: Determine exact values of ar⋆(n,Kₖ) for k≥5

Question 8.2: Characterize graphs H satisfying ar⋆(n,H) = Θ(n)

• Known: ea(H)≥3 ⟹ ar⋆(n,H) is superlinear
• Conjecture: ea(H)=2 ⟹ ar⋆(n,H) = Θ(n)

Question 8.5: Prove or disprove ar⋆(n,H) = Θ(n) when ea(H)=2

Other Directions:

• 3-dimensional hypercube Q₃: ar⋆(n,Q₃) ≥ 2n+21, is it Θ(n)?
• Behavior of 4-regular graphs
• More precise bounds for tree joins

In-Depth Evaluation

Strengths

1. Technical Depth:
   • The K₄ proof is extremely refined, introducing hierarchical concepts of good tuples, great, restricted tuples
   • Innovative combination of multiple technical tools (oriented graphs, auxiliary graphs, induction)
2. Completeness of Results:
   • Provides not just numerical values but also characterizes extremal coloring structures (Cₖ, K₄⁻)
   • Systematic study from specific graphs to general graph classes (tree joins)
3. Theoretical Contributions:
   • Fills important gap in Axenovich-Iverson results
   • Establishes deep connections between star coloring and extremal graph theory
   • Introduces new problem of star-realizable densities
4. Clear Presentation:
   • Well-structured, progressing from simple to complex
   • Sufficient lemma scaffolding
   • Clear proof strategy explanations
5. Methodological Innovation:
   • Systematizes modified coloring techniques
   • Good tuple framework handles complex constraints
   • Novel application of dependent random choice to coloring problems

Weaknesses

1. Extremal Colorings for K₄ Not Completely Characterized:
   • Paper acknowledges multiple extremal colorings exist but provides no complete classification
   • While possibly inherent to the problem, leaves theoretical gap
2. Some Proofs Lengthy:
   • K₄ proof occupies substantial space (Section 6)
   • While necessary, may impact readability
3. Existence of Gaps:
   • K₅⁻ upper and lower bounds differ by constant factor 16
   • Tree join bounds not sufficiently tight
4. Many Open Problems:
   • While important problems are raised, many basic cases (e.g., Kₖ, k≥5) remain unresolved
   • Conjecture for ea(H)=2 unproven
5. Limited Application Discussion:
   • As pure mathematics paper, no discussion of potential applications
   • Connections to computer science and network theory unexplored

Impact

1. Theoretical Impact:
   • Initiates systematic study of star coloring anti-Ramsey theory
   • Provides methodology for handling va(H)=2 cases
   • Bridges multiple combinatorics branches
2. Directions for Future Research:
   • Stimulates research on star-realizable densities
   • Advances theory for ea(H)=2 cases
   • Provides concrete problems for subsequent research
3. Technical Contributions:
   • Good tuple method potentially applicable to other coloring problems
   • Modified coloring construction techniques generalizable
   • New applications of dependent random choice
4. Limitations:
   • As pure theory, direct applications limited
   • Requires substantial combinatorics background for comprehension

Applicable Scenarios

1. Theoretical Research:
   • Extremal graph theory researchers
   • Ramsey theory researchers
   • Graph coloring theory researchers
2. Related Problems:
   • Vertex/edge arboricity research
   • Generalized Ramsey numbers
   • Extremal density realization problems
3. Method Borrowing:
   • Coloring problems requiring fine structural analysis
   • Problems needing extremal example construction
   • Problems involving oriented graph analysis

Key References

1. Erdős, Simonovits, Sós (1975): Anti-Ramsey theorems - Foundational work in anti-Ramsey theory
2. Axenovich, Iverson (2008): Edge-colorings avoiding rainbow and monochromatic subgraphs - Directly extended by this paper
3. Erdős, Stone (1946): On the structure of linear graphs - Fundamental theorem in extremal graph theory
4. Kővári, Sós, Turán (1954): On a problem of K. Zarankiewicz - Classical result on Zarankiewicz problem
5. Fox, Sudakov (2011): Dependent random choice - Key probabilistic tool used in this paper

Overall Assessment: This is a high-quality theoretical combinatorics paper that systematically studies the anti-Ramsey problem for star-colored graphs, providing exact or asymptotic results in multiple important cases. The technical depth is substantial, particularly the K₄ proof demonstrating sophisticated combinatorial techniques. The paper not only solves specific problems but establishes a methodological framework for addressing such problems and raises important open questions. For researchers in extremal graph theory and Ramsey theory, this is essential reading.