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

DOI10.1007/S00373-019-02026-1MaRDI QIDQ2000563zbMATH OpenOpenAlexFDO

Authors Nika Salia, Casey Tompkins, Oscar Zamora

Publication date 28 June 2019

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

Copyright license Creative Commons Attribution 4.0 International

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)

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.

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; zbMATH DE number 5130735
• A structural theorem on embedded graphs and its application to colorings

Cites work

• scientific article; zbMATH DE number 861349 (Why is no real title available?)
• scientific article; zbMATH DE number 3258067 (Why is no real title available?)
• scientific article; zbMATH DE number 3262986 (Why is no real title available?)
• 3-uniform hypergraphs avoiding a given odd cycle
• Extremal numbers for odd cycles
• On maximal paths and circuits of graphs
• The Erdős‐Sós Conjecture for trees of diameter four

Cited in

(5)

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

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)