On a Conjecture of Thomassen

descriptionPublicationkeyboard_double_arrow_right Article , Preprint 01 Jul 2015Embargo end date: 01 Oct 2014 United States Publisher:The Electronic Journal of CombinatoricsJournal:The Electronic Journal of Combinatorics, volume 22 (eissn: 1077-8926,

Copyright policy )Funded by:NSF | Graduate Research Fellows...

Authors: Delcourt, Michelle; Ferber, Asaf;

doi: 10.37236/4762 , 10.48550/arxiv.1410.4902

arXiv: 1410.4902

handle: 1721.1/98409

On a Conjecture of Thomassen

- Summary
- Subjects
- Metrics

Abstract

In 1989, Thomassen asked whether there is an integer-valued function $f(k)$ such that every $f(k)$-connected graph admits a spanning, bipartite $k$-connected subgraph. In this paper we take a first, humble approach, showing the conjecture is true up to a $\log n$ factor.

Country

United States

Related Organizations

University of Illinois at Urbana Champaign
United States
Massachusetts Institute of Technology
United States
Yale University
United States
University of Illinois at Urbana-Champaign
United States

Keywords

Connectivity, graph connectivity, FOS: Mathematics, Directed graphs (digraphs), tournaments, Mathematics - Combinatorics, Combinatorics (math.CO), Thomassen, digraphs

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	3
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average