On the structure of (banner, odd hole)-free graphs

DOI10.1002/JGT.22258MaRDI QIDQ4646946zbMATH OpenOpenAlexWikidataFDO

Authors Chính T. Hoàng

Publication date 3 January 2019

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.02324

zbMATH Keywords

perfect graphodd holebanner

Mathematics Subject Classification ID

Perfect graphs (05C17)

Abstract: 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 which 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 $omeg{a}^2$ where $omega$ denotes the number of vertices in a largest clique of $G$. We prove that (banner, odd hole)-free graphs are perfect-divisible. %

Recommendations

• On the structure of (pan, even hole)-free graphs
• Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
• Structure and algorithms for (cap, even hole)-free graphs
• Even-hole-free graphs part II: Recognition algorithm
• Even and odd holes in cap-free graphs

Cited in

(11)

• Even-hole-free graphs: A survey
• On the chromatic number of some \(P_5\)-free graphs
• Perfect divisibility and coloring of some fork-free graphs
• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• 2-divisibility of some odd hole free graphs
• Coloring graph classes with no induced fork via perfect divisibility
• Coloring of some crown-free graphs
• Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions
• Triangle packings and transversals of some \(K_{4}\)-free graphs
• On the chromatic number of a family of odd hole free graphs
• Divisibility and coloring of some \(P_5\)-free graphs

This page was built for publication: On the structure of (banner, odd hole)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4646946)