Source author record

Stephen G. Hartke

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics math.AC

Catalog footprint

Research overview

11works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2017arXiv

Navigating Between Packings of Graphic Sequences

Let $π_1=(d_1^{(1)}, \ldots,d_n^{(1)})$ and $π_2=(d_1^{(2)},\ldots,d_n^{(2)})$ be graphic sequences. We say they \emph{pack} if there exist edge-disjoint realizations $G_1$ and $G_2$ of $π_1$ and $π_2$ , respectively, on vertex set $\{v_1,\dots,v_n\}$ such that for $j\in\{1,2\}$ , $d_{G_j}(v_i)=d_i^{(j)}$ for all $i\in\{1,\ldots,n\}$ . In this case, we say that $(G_1,G_2)$ is a $(π_1,π_2)$ -\textit{packing}. A clear necessary condition for graphic sequences $π_1$ and $π_2$ to pack is that $π_1+π_2$ , their componentwise sum, is also graphic. It is known, however, that this condition is not sufficient, and furthermore that the general problem of determining if two sequences pack is $NP$ - complete. S.~Kundu proved in 1973 that if $π_2$ is almost regular, that is each element is from $\{k-1, k\}$ , then $π_1$ and $π_2$ pack if and only if $π_1+π_2$ is graphic. In this paper we will consider graphic sequences $π$ with the property that $π+\mathbf{1}$ is graphic. By Kundu's theorem, the sequences $π$ and $\mathbf{1}$ pack, and there exist edge-disjoint realizations $G$ and $\mathcal{I}$ , where $\mathcal{I}$ is a 1-factor. We call such a $(π,\mathbf{1})$ packing a {\em Kundu realization}. Assume that $π$ is a graphic sequence, in which each term is at most $n/24$ , that packs with $\mathbf{1}$ . This paper contains two results. On one hand, any two Kundu realizations of the degree sequence $π+\mathbf{1}$ can be transformed into each other through a sequence of other Kundu realizations by swap operations. On the other hand, the same conditions ensure that any particular 1-factor can be part of a Kundu realization of $π+\mathbf{1}$ .

preprint2016arXiv

The chromatic number of the square of subcubic planar graphs

Wegner conjectured in 1977 that the square of every planar graph with maximum degree at most $3$ is $7$ -colorable. We prove this conjecture using the discharging method and computational techniques to verify reducible configurations.

preprint2015arXiv

On the Strong Chromatic Index of Sparse Graphs

The strong chromatic index of a graph $G$ , denoted $χ_s'(G)$ , is the least number of colors needed to edge-color $G$ so that edges at distance at most two receive distinct colors. The strong list chromatic index, denoted $χ_{s,\ell}'(G)$ , is the least integer $k$ such that if arbitrary lists of size $k$ are assigned to each edge then $G$ can be edge-colored from those lists where edges at distance at most two receive distinct colors. We use the discharging method, the Combinatorial Nullstellensatz, and computation to show that if $G$ is a subcubic planar graph with $\operatorname{girth}(G) \geq 41$ then $χ_{s,\ell}'(G) \leq 5$ , answering a question of Borodin and Ivanova [Precise upper bound for the strong edge chromatic number of sparse planar graphs, Discuss. Math. Graph Theory, 33(4), (2014) 759--770]. We further show that if $G$ is a subcubic planar graph and $\operatorname{girth}(G) \geq 30$ , then $χ_s'(G) \leq 5$ , improving a bound from the same paper. Finally, if $G$ is a planar graph with maximum degree at most four and $\operatorname{girth}(G) \geq 28$ , then $χ_s'(G) \leq 7$ , improving a more general bound of Wang and Zhao from [Odd graphs and its application on the strong edge coloring, arXiv:1412.8358] in this case.

preprint2014arXiv

Extending Precolorings to Distinguish Group Actions

Given a group $Γ$ acting on a set $X$ , a $k$ -coloring $ϕ:X\to\{1,\dots,k\}$ of $X$ is distinguishing with respect to $Γ$ if the only $γ\in Γ$ that fixes $ϕ$ is the identity action. The distinguishing number of the action $Γ$ , denoted $D_Γ(X)$ , is then the smallest positive integer $k$ such that there is a distinguishing $k$ -coloring of $X$ with respect to $Γ$ . This notion has been studied in a number of settings, but by far the largest body of work has been concerned with finding the distinguishing number of the action of the automorphism group of a graph $G$ upon its vertex set, which is referred to as the distinguishing number of $G$ . The distinguishing number of a group action is a measure of how difficult it is to "break" all of the permutations arising from that action. In this paper, we aim to further differentiate the resilience of group actions with the same distinguishing number. In particular, we introduce a precoloring extension framework to address this issue. A set $S \subseteq X$ is a fixing set for $Γ$ if for every non-identity element $γ\in Γ$ there is an element $s \in S$ such that $γ(s) \neq s$ . The distinguishing extension number $\operatorname{ext}_D(X,Γ;k)$ is the minimum number $m$ such that for all fixing sets $W \subseteq X$ with $|W| \geq m$ , every $k$ -coloring $c : X \setminus W \to [k]$ can be extended to a $k$ -coloring that distinguishes $X$ . In this paper, we prove that $\operatorname{ext}_D(\mathbb{R},\operatorname{Aut}(\mathbb{R}),2) =4$ , where $\operatorname{Aut}(\mathbb{R})$ is comprised of compositions of translations and reflections. We also consider the distinguishing extension number of the circle and (finite) cycles, obtaining several exact results and bounds.

preprint2014arXiv

On the independence ratio of distance graphs

A distance graph is an undirected graph on the integers where two integers are adjacent if their difference is in a prescribed distance set. The independence ratio of a distance graph $G$ is the maximum density of an independent set in $G$ . Lih, Liu, and Zhu [Star extremal circulant graphs, SIAM J. Discrete Math. 12 (1999) 491--499] showed that the independence ratio is equal to the inverse of the fractional chromatic number, thus relating the concept to the well studied question of finding the chromatic number of distance graphs. We prove that the independence ratio of a distance graph is achieved by a periodic set, and we present a framework for discharging arguments to demonstrate upper bounds on the independence ratio. With these tools, we determine the exact independence ratio for several infinite families of distance sets of size three, determine asymptotic values for others, and present several conjectures.

preprint2014arXiv

The Alpha Problem & Line Count Configurations

Motivated by the work of Chudnovsky and the Eisenbud-Mazur Conjecture on evolutions, Harbourne and Huneke give a series of conjectures that relate symbolic and regular powers of ideals of fat points in $\mathbb P^n$ . The conjectures involve both containment statements and bounds for the initial degree in which there is a non-zero form in an ideal. Working with initial degrees, we verify two of these conjectures for special line count configurations in projective 2-space over an algebraically closed field of characteristic 0.

preprint2013arXiv

A Branch-and-Cut Strategy for the Manickam-Miklos-Singhi Conjecture

The Manickam-Miklos-Singhi Conjecture states that when n is at least 4k, every multiset of n real numbers with nonnegative total sum has at least (n-1 choose k-1) k-subsets with nonnegative sum. We develop a branch-and-cut strategy using a linear programming formulation to show that verifying the conjecture for fixed values of k is a finite problem. To improve our search, we develop a zero-error randomized propagation algorithm. Using implementations of these algorithms, we verify a stronger form of the conjecture for all k at most seven.

preprint2013arXiv

Minimal forbidden sets for degree sequence characterizations

Given a set $\mathcal{F}$ of graphs, a graph $G$ is $\mathcal{F}$ -free if $G$ does not contain any member of $\mathcal{F}$ as an induced subgraph. Barrus, Kumbhat, and Hartke [M. D. Barrus, M. Kumbhat, and S. G. Hartke, Graph classes characterized both by forbidden subgraphs and degree sequences, J. Graph Theory (2008), no. 2, 131--148] called $\mathcal{F}$ a degree-sequence-forcing (DSF) set if, for each graph $G$ in the class $\mathcal{C}$ of $\mathcal{F}$ -free graphs, every realization of the degree sequence of $G$ is also in $\mathcal{C}$ . A DSF set is minimal if no proper subset is also DSF. In this paper, we present new properties of minimal DSF sets, including that every graph is in a minimal DSF set and that there are only finitely many DSF sets of cardinality $k$ . Using these properties and a computer search, we characterize the minimal DSF triples.

preprint2012arXiv

Uniquely K_r-Saturated Graphs

A graph G is uniquely K_r-saturated if it contains no clique with r vertices and if for all edges e in the complement, G + e has a unique clique with r vertices. Previously, few examples of uniquely K_r-saturated graphs were known, and little was known about their properties. We search for these graphs by adapting orbital branching, a technique originally developed for symmetric integer linear programs. We find several new uniquely K_r-saturated graphs with 4 \leq r \leq 7, as well as two new infinite families based on Cayley graphs for Z_n with a small number of generators.

preprint2011arXiv

List Distinguishing Parameters of Trees

A coloring of the vertices of a graph G is said to be distinguishing} provided no nontrivial automorphism of G preserves all of the vertex colors. The distinguishing number of G, D(G), is the minimum number of colors in a distinguishing coloring of G. The distinguishing chromatic number of G, chi_D(G), is the minimum number of colors in a distinguishing coloring of G that is also a proper coloring. Recently the notion of a distinguishing coloring was extended to that of a list distinguishing coloring. Given an assignment L= {L(v) : v in V(G)} of lists of available colors to the vertices of G, we say that G is (properly) L-distinguishable if there is a (proper) distinguishing coloring f of G such that f(v) is in L(v) for all v. The list distinguishing number of G, D_l(G), is the minimum integer k such that G is L-distinguishable for any list assignment L with |L(v)| = k for all v. Similarly, the list distinguishing chromatic number of G, denoted chi_{D_l}(G) is the minimum integer k such that G is properly L-distinguishable for any list assignment L with |L(v)| = k for all v. In this paper, we study these distinguishing parameters for trees, and in particular extend an enumerative technique of Cheng to show that for any tree T, D_l(T) = D(T), chi_D(T)=chi_{D_l}(T), and chi_D(T) <= D(T) + 1.

preprint2010arXiv

On the hardness of recognizing triangular line graphs

Given a graph G, its triangular line graph is the graph T(G) with vertex set consisting of the edges of G and adjacencies between edges that are incident in G as well as being within a common triangle. Graphs with a representation as the triangular line graph of some graph G are triangular line graphs, which have been studied under many names including anti-Gallai graphs, 2-in-3 graphs, and link graphs. While closely related to line graphs, triangular line graphs have been difficult to understand and characterize. Van Bang Le asked if recognizing triangular line graphs has an efficient algorithm or is computationally complex. We answer this question by proving that the complexity of recognizing triangular line graphs is NP-complete via a reduction from 3-SAT.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Stephen G. Hartke

Research overview

Is this your work?

11 publications

Navigating Between Packings of Graphic Sequences

The chromatic number of the square of subcubic planar graphs

On the Strong Chromatic Index of Sparse Graphs

Extending Precolorings to Distinguish Group Actions

On the independence ratio of distance graphs

The Alpha Problem & Line Count Configurations

A Branch-and-Cut Strategy for the Manickam-Miklos-Singhi Conjecture

Minimal forbidden sets for degree sequence characterizations

Uniquely K_r-Saturated Graphs

List Distinguishing Parameters of Trees

On the hardness of recognizing triangular line graphs

See the researcher in context

Building this map preview