Journal: Journal of Graph Theory

Abbreviation

J. graph theory

Publisher

Wiley

Journal Volumes

ISSN

0364-9024
1097-0118

Description

Filters

Reset filters

Search Results

Publications 1 - 10 of 28
  • Oriented discrepancy of Hamilton cycles
    Item type: Journal Article
    Gishboliner, Lior; Krivelevich, Michael; Michaeli, Peleg (2023)
    Journal of Graph Theory
    We propose the following extension of Dirac's theorem: if G is a graph with n >= 3 vertices and minimum degree delta(G) >= n/2, then in every orientation of G there is a Hamilton cycle with at least δ(G) edges oriented inthe same direction. We prove an approximate versionof this conjecture, showing that minimum degree (n+8k)/2 guarantees a Hamilton cycle with at least (n+k)/2 edges oriented in the same direction. We also study the analogous problem for random graphs, showing that if the edge probability p=p(n) is above the Hamiltonicity threshold, then, with high probability, in every orientation of G similar to G(n,p) there is a Hamilton cycle with (1-o(1))n edges oriented in the same direction.
  • On the minimum degree of minimal Ramsey graphs
    Item type: Journal Article
    Szabó, Tibor; Zumstein, Philipp; Zürcher, Stefanie (2010)
    Journal of Graph Theory
  • The maximum number of induced C5's in a planar graph
    Item type: Journal Article
    Ghosh, Debarun; Gyori, Ervin; Janzer, Oliver; et al. (2022)
    Journal of Graph Theory
    Finding the maximum number of induced cycles of length k in a graph on n vertices has been one of the most intriguing open problems of Extremal Graph Theory. Recently Balogh, Hu, Lidicky and Pfender answered the question in the case k=5. In this paper we determine precisely, for all sufficiently large n, the maximum number of induced 5-cycles that an n-vertex planar graph can contain.
  • Calculating Ramsey Numbers by Partitioning Colored Graphs
    Item type: Journal Article
    Pokrovskiy, Alexey (2017)
    Journal of Graph Theory
  • On Antimagic Directed Graphs
    Item type: Journal Article
    Hefetz, Dan; Mütze, Torsten; Schwartz, Justus (2010)
    Journal of Graph Theory
  • Subdigraphs of prescribed size and out-degree
    Item type: Journal Article
    Steiner, Raphael (2024)
    Journal of Graph Theory
    In 2006, Noga Alon raised the following open problem: Does there exist an absolute constant c > 0 such that every 2n-vertex digraph with minimum out-degree at least s contains an n-vertex subdigraph with minimum out-degree at least s/2 - c? In this note, we answer this natural question in the negative, by showing that for arbitrarily large values of n there exists a 2n-vertex tournament with minimum out-degree s = n -1, in which every n-vertex subdigraph contains a vertex of out-degree at most s/2 - (1/2 + o(1))log₃(s).
  • The generalized acyclic edge chromatic number of random regular graphs
    Item type: Journal Article
    Gerke, Stefanie; Greenhill, Catherine; Wormald, Nicholas (2006)
    Journal of Graph Theory
  • Partitioning a graph into monochromatic connected subgraphs
    Item type: Journal Article
    Girão, António; Letzter, Shoham; Sahasrabudhe, Julian (2019)
    Journal of Graph Theory
  • Complete minors and average degree: A short proof
    Item type: Journal Article
    Alon, Noga; Krivelevich, Michael; Sudakov, Benny (2023)
    Journal of Graph Theory
    We provide a short and self-contained proof of the classical result of Kostochka and of Thomason, ensuring that every graph of average degree d $d$ has a complete minor of order omega(d/logd) ${\rm{\Omega }}(d\unicode{x02215}\sqrt{{\rm{log}}d})$.
  • A generalization of Turan's theorem
    Item type: Journal Article
    Sudakov, Benny; Szabó, Tibor; Van Vu, H. (2005)
    Journal of Graph Theory
Publications 1 - 10 of 28