Coloring graphs with no induced five-vertex path or gem

Maria Chudnovsky; T. Karthick; Peter Maceli; Frédéric Maffray

doi:10.1002/jgt.22572

Coloring graphs with no induced five-vertex path or gem

Maria Chudnovsky, T. Karthick, Peter Maceli, Frédéric Maffray

Mathematics

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

20 Scopus citations

Abstract

For a graph (Formula presented.), let (Formula presented.) and (Formula presented.), respectively, denote the chromatic number and clique number of (Formula presented.). We give an explicit structural description of ((Formula presented.), gem)-free graphs, and show that every such graph (Formula presented.) satisfies (Formula presented.). Moreover, this bound is best possible. Here a gem is the graph that consists of an induced four-vertex path plus a vertex which is adjacent to all the vertices of that path.

Original language	English (US)
Pages (from-to)	527-542
Number of pages	16
Journal	Journal of Graph Theory
Volume	95
Issue number	4
DOIs	https://doi.org/10.1002/jgt.22572
State	Published - Dec 1 2020

All Science Journal Classification (ASJC) codes

Geometry and Topology

Keywords

P-free graphs
chromatic number
clique number
χ-boundedness

Access to Document

10.1002/jgt.22572

Cite this

@article{13e8f75797334320aa0ee199aa8d7720,

title = "Coloring graphs with no induced five-vertex path or gem",

abstract = "For a graph (Formula presented.), let (Formula presented.) and (Formula presented.), respectively, denote the chromatic number and clique number of (Formula presented.). We give an explicit structural description of ((Formula presented.), gem)-free graphs, and show that every such graph (Formula presented.) satisfies (Formula presented.). Moreover, this bound is best possible. Here a gem is the graph that consists of an induced four-vertex path plus a vertex which is adjacent to all the vertices of that path.",

keywords = "P-free graphs, chromatic number, clique number, χ-boundedness",

author = "Maria Chudnovsky and T. Karthick and Peter Maceli and Fr{\'e}d{\'e}ric Maffray",

note = "Publisher Copyright: {\textcopyright} 2020 Wiley Periodicals, Inc.",

year = "2020",

month = dec,

day = "1",

doi = "10.1002/jgt.22572",

language = "English (US)",

volume = "95",

pages = "527--542",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "4",

}

TY - JOUR

T1 - Coloring graphs with no induced five-vertex path or gem

AU - Chudnovsky, Maria

AU - Karthick, T.

AU - Maceli, Peter

AU - Maffray, Frédéric

PY - 2020/12/1

Y1 - 2020/12/1

N2 - For a graph (Formula presented.), let (Formula presented.) and (Formula presented.), respectively, denote the chromatic number and clique number of (Formula presented.). We give an explicit structural description of ((Formula presented.), gem)-free graphs, and show that every such graph (Formula presented.) satisfies (Formula presented.). Moreover, this bound is best possible. Here a gem is the graph that consists of an induced four-vertex path plus a vertex which is adjacent to all the vertices of that path.

AB - For a graph (Formula presented.), let (Formula presented.) and (Formula presented.), respectively, denote the chromatic number and clique number of (Formula presented.). We give an explicit structural description of ((Formula presented.), gem)-free graphs, and show that every such graph (Formula presented.) satisfies (Formula presented.). Moreover, this bound is best possible. Here a gem is the graph that consists of an induced four-vertex path plus a vertex which is adjacent to all the vertices of that path.

KW - P-free graphs

KW - chromatic number

KW - clique number

KW - χ-boundedness

UR - http://www.scopus.com/inward/record.url?scp=85083955106&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85083955106&partnerID=8YFLogxK

U2 - 10.1002/jgt.22572

DO - 10.1002/jgt.22572

M3 - Article

AN - SCOPUS:85083955106

SN - 0364-9024

VL - 95

SP - 527

EP - 542

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 4

ER -

Coloring graphs with no induced five-vertex path or gem

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this