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

Nika Salia; Casey Tompkins; Oscar Zamora

doi:10.1007/s00373-019-02026-1

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

Nika Salia
, Casey Tompkins^*
, Oscar Zamora

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

While investigating odd-cycle free hypergraphs, Győri and Lemons introduced a colored version of the classical theorem of Erdő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 end vertices of different colors has at most 2kn edges. We show that Erdő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 Erdős-Sós conjecture.

Original language	English
Pages (from-to)	689-694
Number of pages	6
Journal	Graphs and Combinatorics
Volume	35
Issue number	3
DOIs	https://doi.org/10.1007/s00373-019-02026-1
State	Published - May 2019
Externally published	Yes

Bibliographical note

Publisher Copyright:
© The Author(s) 2019.

Keywords

Cycles
Extremal
Paths
Trees
Vertex colored

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/s00373-019-02026-1

Cite this

@article{9f5c80f365ec4988bb0754c1a5fdedcf,

title = "An Erd{\H o}s-Gallai type theorem for vertex colored graphs",

abstract = "While investigating odd-cycle free hypergraphs, Gy{\H o}ri and Lemons introduced a colored version of the classical theorem of Erd{\H o}s and Gallai on Pk-free graphs. They proved that any graph G with a proper vertex coloring and no path of length 2k + 1 with end vertices of different colors has at most 2kn edges. We show that Erd{\H o}s and Gallai{\textquoteright}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 Erd{\H o}s-S{\'o}s conjecture.",

keywords = "Cycles, Extremal, Paths, Trees, Vertex colored",

author = "Nika Salia and Casey Tompkins and Oscar Zamora",

note = "Publisher Copyright: {\textcopyright} The Author(s) 2019.",

year = "2019",

month = may,

doi = "10.1007/s00373-019-02026-1",

language = "English",

volume = "35",

pages = "689--694",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "3",

}

TY - JOUR

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

AU - Salia, Nika

AU - Tompkins, Casey

AU - Zamora, Oscar

N1 - Publisher Copyright: © The Author(s) 2019.

PY - 2019/5

Y1 - 2019/5

N2 - While investigating odd-cycle free hypergraphs, Győri and Lemons introduced a colored version of the classical theorem of Erdős and Gallai on Pk-free graphs. They proved that any graph G with a proper vertex coloring and no path of length 2k + 1 with end vertices of different colors has at most 2kn edges. We show that Erdő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 Erdős-Sós conjecture.

AB - While investigating odd-cycle free hypergraphs, Győri and Lemons introduced a colored version of the classical theorem of Erdős and Gallai on Pk-free graphs. They proved that any graph G with a proper vertex coloring and no path of length 2k + 1 with end vertices of different colors has at most 2kn edges. We show that Erdő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 Erdős-Sós conjecture.

KW - Cycles

KW - Extremal

KW - Paths

KW - Trees

KW - Vertex colored

UR - https://www.scopus.com/pages/publications/85062778324

U2 - 10.1007/s00373-019-02026-1

DO - 10.1007/s00373-019-02026-1

M3 - Article

AN - SCOPUS:85062778324

SN - 0911-0119

VL - 35

SP - 689

EP - 694

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 3

ER -

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

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this