The Second Neighborhood Conjecture for Oriented Graphs Missing Combs

arXiv1602.08631MaRDI QIDQ6270910FDOQ6270910

Salman Ghazal

Publication date: 27 February 2016

Abstract: Seymour's Second Neighborhood Conjecture asserts that every oriented graph has a vertex whose first out-neighborhood is at most as large as its second out-neighborhood. Combs are the graphs having no induced $C_4$, $overline{C}_4$, $C_5$, chair or $overlinechair$. We characterize combs using dependency digraphs. We characterize the graphs having no induced $C_4$, $overline{C}_4$, chair or $overlinechair$ using dependency digraphs. Then we prove that every oriented graph missing a comb satisfies this conjecture. We then deduce that every oriented comb and every oriented threshold graph satisfies Seymour's conjecture.

This page was built for publication: The Second Neighborhood Conjecture for Oriented Graphs Missing Combs

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