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

DOI10.1002/JGT.22258zbMATH Open1440.05100arXiv1510.02324OpenAlexW2964056504WikidataQ129908881 ScholiaQ129908881MaRDI QIDQ4646946FDOQ4646946

Authors: Chính T. Hoàng 

Publication date: 3 January 2019

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

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. %

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

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

zbMATH Keywords

perfect graphodd holebanner

Mathematics Subject Classification ID

Perfect graphs (05C17)

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)