Premium
On the structure of (banner, odd hole)‐free graphs
Author(s) -
Hoàng Chính T.
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22258
Subject(s) - combinatorics , mathematics , induced subgraph , wheel graph , chordal graph , perfect graph , vertex (graph theory) , discrete mathematics , split graph , perfect graph theorem , neighbourhood (mathematics) , graph , graph power , 1 planar graph , line graph , pathwidth , mathematical analysis
A hole is a chordless cycle with at least four vertices. A hole is odd if it has an odd number of vertices. A banner is a graph that consists of a hole on four vertices and a single vertex with precisely one neighbor on the hole. We prove that a (banner, odd hole)‐free graph is perfect, or does not contain a stable set on three vertices, or contains a homogeneous set. Using this structure result, we design a polynomial‐time algorithm for recognizing (banner, odd hole)‐free graphs. We also design polynomial‐time algorithms to find, for such a graph, a minimum coloring, and largest stable set. A graph G is perfectly divisible if every induced subgraph H of G contains a set X of vertices such that X meets all largest cliques of H , and X induces a perfect graph. The chromatic number of a perfectly divisible graph G is bounded by ω 2 where ω denotes the number of vertices in a largest clique of G . We prove that (banner, odd hole)‐free graphs are perfectly divisible.