An Erdős-Gallai type theorem for vertex colored graphs

DOI10.1007/S00373-019-02026-1zbMATH Open1416.05115arXiv1712.04388OpenAlexW2772382996MaRDI QIDQ2000563FDOQ2000563

Oscar Zamora, Nika Salia, Casey Tompkins

Publication date: 28 June 2019

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: While investigating odd-cycle free hypergraphs, GyH{o}ri and Lemons introduced a colored version of the classical theorem of ErdH{o}s and Gallai on $P_k$-free graphs. They proved that any graph $G$ with a proper vertex coloring and no path of length $2k+1$ with endpoints of different colors has at most $2kn$ edges. We show that ErdH{o}s and Gallai's original sharp upper bound of $kn$ holds for their problem as well. We also introduce a version of this problem for trees and present a generalization of the ErdH{o}s-S'os conjecture.

Full work available at URL: https://arxiv.org/abs/1712.04388

zbMATH Keywords

treespathscyclesvertex coloringextremal

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On maximal paths and circuits of graphs
• The Erdős‐Sós Conjecture for trees of diameter four
• 3-uniform hypergraphs avoiding a given odd cycle
• Extremal Numbers for Odd Cycles

Cited In (4)

• An extension of Richardson's theorem in m-colored digraphs
• The Erdős–Rothschild problem on edge-colourings with forbidden monochromatic cliques
• How connectivity affects the extremal number of trees
• Note on Gy. Elekes's conjectures concerning unavoidable patterns in proper colorings

   Recommendations

• On a theorem about vertex colorings of graphs 👍 👎
• Erdős-Gallai-type results for colorful monochromatic connectivity of a graph 👍 👎
• Some generalizations of theorems on vertex coloring 👍 👎
• Tverberg's theorem and graph coloring 👍 👎
• A Cvetković-type theorem for coloring of digraphs 👍 👎
• Erdős-Ko-Rado-type theorems for colored sets 👍 👎
• A conjecture of a vertex-distinguishing edge coloring of graphs 👍 👎
• Bounded vertex colorings of graphs 👍 👎
• Title not available (Why is that?) 👍 👎
• A structural theorem on embedded graphs and its application to colorings 👍 👎

This page was built for publication: An Erdős-Gallai type theorem for vertex colored graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2000563)