Details

Autor(en) / Beteiligte

• González-Moreno, Diego
• Guevara, Mucuy-Kak
• Montellano-Ballesteros, Juan José

Titel

An Anti-Ramsey Theorem of k-Restricted Edge-Cuts

Ist Teil von

• Graphs and combinatorics, 2022-08, Vol.38 (4), Article 125

Ort / Verlag

Tokyo: Springer Japan

Erscheinungsjahr

2022

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• Given a graph G (with multiple edges allowed), a k-restricted edge-cut of G is an edge-cut R ⊆ E ( G ) of G such that every connected component in G - R has order at least k . A graph G is λ k - connected if k -restricted edge cuts exist. Given an edge-coloring of G , an edge-cut of G will be called heterochromatic if all its edges receive different colors. Given a graph G and an integer k ≥ 2 , let h ( G ,  k ) be the minimum integer p such that every p -coloring of the edges of G produces an heterochromatic k -restricted edge-cut of G . In this paper we prove that for a λ k -connected graph G of size m , order n ≥ 3 k - 2 , and with no k -restricted edge-cut of size 1, we have that m - n + min { κ 0 ( G ) - 2 , t ( G , k ) } + 2 ≤ h ( G , k ) ≤ m - n + t ( G , k ) + 2 , where κ 0 ( G ) is the vertex-connectivity of G and t ( G ,  k ) is the maximum cardinality of a set S ⊆ V ( G ) such that the connected components in G [ S ] have order at most k - 1 . As a corollary we see that h ( G , k ) ≤ m - n + α ( G ) ( k - 1 ) + 2 , with α ( G ) the independence number of G .