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

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
• scientific article
• A structural theorem on embedded graphs and its application to colorings

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

• On maximal paths and circuits of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Erdős‐Sós Conjecture for trees of diameter four
• Title not available (Why is that?)
• 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

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)