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

6 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

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",

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

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 - https://www.scopus.com/pages/publications/84975705704

UR - https://www.scopus.com/pages/publications/84975705704#tab=citedBy

U2 - 10.1002/jgt.22025

DO - 10.1002/jgt.22025

M3 - Article

AN - SCOPUS:84975705704

SN - 0364-9024

VL - 84

SP - 262

EP - 285

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 3

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this