SHStephen G. Hartke

Stephen G. Hartke

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Stephen G. Hartke has a total of 38 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Domination of subcubic planar graphs with large girth

    by Eun-Kyung Cho, Eric Culver, Stephen G. Hartke, Vesna Iršič Chenoweth

    AMC is a journal published by University of Primorska.

  • Open Access

    Reconstruction of C_4-free graphs from the set of closed neighborhoods and digital convexity

    by Steffen Borgwardt, MacKenzie Carr, Ce Chen, Wayne Ge, Stephen G. Hartke, Yixuan Huang, Alex Moon

    Fomin, Kratochvíl, Lokshtanov, Mancini, and Telle showed that every $C_{4}$-free graph is reconstructible from the \emph{multiset} of closed neighborhoods. We strengthen their result proving that every $C_{4}$-free graph is reconstructible from the \emph{set} of closed neighborhoods. This extends the work of Lafrance et al.\ by showing that all $C_{4}$-free graphs, and hence all graphs of girth at least five, are reconstructible from their digitally convex sets. A subset $S$ of vertices in a graph $G$ is digitally convex if, for every vertex $v \notin S$, there is a private neighbor of $v$. We establish that reconstruction from digitally convex sets is equivalent to reconstruction from the set of closed neighborhoods.

  • Open Access

    The forb-flex method for odd coloring and proper conflict-free coloring of planar graphs

    by James Anderson, Herman Chau, Eun-Kyung Cho, Nicholas Crawford, Stephen G. Hartke, Emily Heath, Owen Henderschedt, Hyemin Kwon, Zhiyuan Zhang

    We introduce a new tool useful for greedy coloring, which we call the forb-flex method, and apply it to odd coloring and proper conflict-free coloring of planar graphs. The odd chromatic number, denoted $χ_{\mathsf{o}}(G)$, is the smallest number of colors needed to properly color $G$ such that every non-isolated vertex of $G$ has a color appearing an odd number of times in its neighborhood. The proper conflict-free chromatic number, denoted $χ_{\mathsf{PCF}}(G)$, is the smallest number of colors needed to properly color $G$ such that every non-isolated vertex of $G$ has a color appearing uniquely in its neighborhood. Our new tool works by carefully counting the structures in the neighborhood of a vertex and determining if a neighbor of a vertex can be recolored at the end of a greedy coloring process to avoid conflicts. Combining this with the discharging method allows us to prove $χ_{\mathsf{PCF}}(G) \leq 4$ for planar graphs of girth at least 11, and $χ_{\mathsf{o}}(G) \leq 4$ for planar graphs of girth at least 10. These results improve upon the recent works of Cho, Choi, Kwon, and Park.

  • Open Access

    Domination of subcubic planar graphs with large girth

    by Eun-Kyung Cho, Eric Culver, Stephen G. Hartke, Vesna Iršič

    Since Reed conjectured in 1996 that the domination number of a connected cubic graph of order $n$ is at most $\lceil \frac13 n \rceil$, the domination number of cubic graphs has been extensively studied. It is now known that the conjecture is false in general, but Henning and Dorbec showed that it holds for graphs with girth at least $9$. Zhu and Wu stated an analogous conjecture for 2-connected cubic planar graphs. In this paper, we present a new upper bound for the domination number of subcubic planar graphs: if $G$ is a subcubic planar graph with girth at least 8, then $γ(G) < n_0 + \frac{3}{4} n_1 + \frac{11}{20} n_2 + \frac{7}{20} n_3$, where $n_i$ denotes the number of vertices in $G$ of degree $i$, for $i \in \{0,1,2,3\}$. We also prove that if $G$ is a subcubic planar graph with girth at least 9, then $γ(G) < n_0 + \frac{13}{17} n_1 + \frac{9}{17} n_2 + \frac{6}{17} n_3$.

  • A Classification of Hyperfocused 12-Arcs

    by Philip DeOrsey, Stephen G. Hartke, Jason Williford

  • Navigating between packings of graphic sequences

    by Péter L. Erdős, Michael Ferrara, Stephen G. Hartke

  • Open Access

    Uniquely $K_r^{(k)}$-Saturated Hypergraphs

    by András GyárFás, Stephen G. Hartke, Charles Viss

    In this paper we generalize the concept of uniquely $K_r$-saturated graphs to hypergraphs. Let $K_r^{(k)}$ denote the complete $k$-uniform hypergraph on $r$ vertices. For integers $k,r,n$ such that $2\leqslant k <r<n$, a $k$-uniform hypergraph $H$ with $n$ vertices is uniquely $K_r^{(k)}$-saturated if $H$ does not contain $K_r^{(k)}$ but adding to $H$ any $k$-set that is not a hyperedge of $H$ results in exactly one copy of $K_r^{(k)}$. Among uniquely $K_r^{(k)}$-saturated hypergraphs, the interesting ones are the primitive ones that do not have a dominating vertex—a vertex belonging to all possible ${n-1\choose k-1}$ edges. Translating the concept to the complements of these hypergraphs, we obtain a natural restriction of $\tau$-critical hypergraphs: a hypergraph $H$ is uniquely $\tau$-critical if for every edge $e$, $\tau(H-e)=\tau(H)-1$ and $H-e$ has a unique transversal of size $\tau(H)-1$.We have two constructions for primitive uniquely $K_r^{(k)}$-saturated hypergraphs. One shows that for $k$ and $r$ where $4\leqslant kr$. This is in contrast to the case $k=2$ and $r=3$ where only the Moore graphs of diameter two have this property. Our other construction keeps $n-r$ fixed; in this case we show that for any fixed $k\ge 2$ there can only be finitely many examples. We give a range for $n$ where these hypergraphs exist. For $n-r=1$ the range is completely determined: $k+1\leqslant n \leqslant {(k+2)^2\over 4}$. For larger values of $n-r$ the upper end of our range reaches approximately half of its upper bound. The lower end depends on the chromatic number of certain Johnson graphs.

  • Extending precolorings to distinguish group actions

    by Michael Ferrara, Ellen Gethner, Stephen G. Hartke, Derrick Stolee, Paul S. Wenger


  • Open Access

    Uniquely $K^{(k)}_r$-saturated Hypergraphs

    by András Gyárfás, Stephen G. Hartke, Charles Viss

    In this paper we generalize the concept of uniquely $K_r$-saturated graphs to hypergraphs. Let $K_r^{(k)}$ denote the complete $k$-uniform hypergraph on $r$ vertices. For integers $k,r,n$ such that $2\le k <r<n$, a $k$-uniform hypergraph $H$ with $n$ vertices is uniquely $K_r^{(k)}$-saturated if $H$ does not contain $K_r^{(k)}$ but adding to $H$ any $k$-set that is not a hyperedge of $H$ results in exactly one copy of $K_r^{(k)}$. Among uniquely $K_r^{(k)}$-saturated hypergraphs, the interesting ones are the primitive ones that do not have a dominating vertex---a vertex belonging to all possible ${n-1\choose k-1}$ edges. Translating the concept to the complements of these hypergraphs, we obtain a natural restriction of $\tau$-critical hypergraphs: a hypergraph $H$ is uniquely $\tau$-critical if for every edge $e$, $\tau(H-e)=\tau(H)-1$ and $H-e$ has a unique transversal of size $\tau(H)-1$. We have two constructions for primitive uniquely $K_r^{(k)}$-saturated hypergraphs. One shows that for $k$ and $r$ where $4\le kr$. This is in contrast to the case $k=2$ and $r=3$ where only the Moore graphs of diameter two have this property. Our other construction keeps $n-r$ fixed; in this case we show that for any fixed $k\ge 2$ there can only be finitely many examples. We give a range for $n$ where these hypergraphs exist. For $n-r=1$ the range is completely determined: $k+1\le n \le {(k+2)^2\over 4}$. For larger values of $n-r$ the upper end of our range reaches approximately half of its upper bound. The lower end depends on the chromatic number of certain Johnson graphs.