4-Coloring P6-Free Graphs with No Induced 5-Cycles

Maria Chudnovsky; Peter Maceli; Juraj Stacho; Mingxian Zhong

doi:10.1002/jgt.22025

4-Coloring P6-Free Graphs with No Induced 5-Cycles

Maria Chudnovsky, Peter Maceli, Juraj Stacho, Mingxian Zhong

Mathematics

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

3 Scopus citations

Abstract

We show that the 4-coloring problem can be solved in polynomial time for graphs with no induced 5-cycle C5 and no induced 6-vertex path P6.

Original language	English (US)
Pages (from-to)	262-285
Number of pages	24
Journal	Journal of Graph Theory
Volume	84
Issue number	3
DOIs	https://doi.org/10.1002/jgt.22025
State	Published - Mar 1 2017

All Science Journal Classification (ASJC) codes

Geometry and Topology

Keywords

algorithm
coloring
induced subgraphs
path

Access to Document

10.1002/jgt.22025

Fingerprint Dive into the research topics of '4-Coloring P6-Free Graphs with No Induced 5-Cycles'. Together they form a unique fingerprint.

Cite this

@article{a076a3ff578343c09659519e2727f9b7,

title = "4-Coloring P6-Free Graphs with No Induced 5-Cycles",

abstract = "We show that the 4-coloring problem can be solved in polynomial time for graphs with no induced 5-cycle C5 and no induced 6-vertex path P6.",

keywords = "algorithm, coloring, induced subgraphs, path",

author = "Maria Chudnovsky and Peter Maceli and Juraj Stacho and Mingxian Zhong",

year = "2017",

month = mar,

day = "1",

doi = "10.1002/jgt.22025",

language = "English (US)",

volume = "84",

pages = "262--285",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "3",

}

TY - JOUR

T1 - 4-Coloring P6-Free Graphs with No Induced 5-Cycles

AU - Chudnovsky, Maria

AU - Maceli, Peter

AU - Stacho, Juraj

AU - Zhong, Mingxian

PY - 2017/3/1

Y1 - 2017/3/1

N2 - We show that the 4-coloring problem can be solved in polynomial time for graphs with no induced 5-cycle C5 and no induced 6-vertex path P6.

AB - We show that the 4-coloring problem can be solved in polynomial time for graphs with no induced 5-cycle C5 and no induced 6-vertex path P6.

KW - algorithm

KW - coloring

KW - induced subgraphs

KW - path

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

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

U2 - 10.1002/jgt.22025

DO - 10.1002/jgt.22025

M3 - Article

AN - SCOPUS:84975705704

VL - 84

SP - 262

EP - 285

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 3

ER -