BZPEER

preprint2022arXiv

In Most 6-regular Toroidal Graphs All 5-colorings are Kempe Equivalent

A Kempe swap in a proper coloring interchanges the colors on some maximal connected 2-colored subgraph. Two $k$ -colorings are $k$ -equivalent if we can transform one into the other using Kempe swaps. The triangulated toroidal grid, $T[m\times n]$ , is formed from (a toroidal embedding of) the Cartesian product of $C_m$ and $C_n$ by adding parallel diagonals inside all 4-faces. Mohar and Salas showed that not all 4-colorings of $T[m\times n]$ are 4-equivalent. In contrast, Bonamy, Bousquet, Feghali, and Johnson showed that all 6-colorings of $T[m\times n]$ are 6-equivalent. They asked whether the same is true for 5-colorings. We answer their question affirmatively when $m,n\ge 6$ . Further, we show that if $G$ is 6-regular with a toroidal embedding where every non-contractible cycle has length at least 7, then all 5-colorings of $G$ are 5-equivalent. Our results relate to the antiferromagnetic Pott's model in statistical mechanics.

preprint2022arXiv

List-Recoloring of Sparse Graphs

Fix a graph $G$ , a list-assignment $L$ for $G$ , and $L$ -colorings $α$ and $β$ . An $L$ -recoloring sequence, starting from $α$ , recolors a single vertex at each step, so that each resulting intermediate coloring is a proper $L$ -coloring. An $L$ -recoloring sequence transforms $α$ to $β$ if its initial coloring is $α$ and its final coloring is $β$ . We prove there exists an $L$ -recoloring sequence that transforms $α$ to $β$ and recolors each vertex at most a constant number of times if (i) $G$ is triangle-free and planar and $L$ is a 7-assignment, or (ii) $\mathrm{mad}(G)<17/5$ and $L$ is a 6-assignment or (iii) $\mathrm{mad}(G)<22/9$ and $L$ is a 4-assignment. Parts (i) and (ii) confirm conjectures of Dvořák and Feghali.

preprint2020arXiv

The Iterated Local Directed Transitivity Model for Social Networks

We introduce a new directed graph model for social networks, based on the transitivity of triads. In the Iterated Local Directed Transitivity (ILDT) model, new nodes are born over discrete time-steps, and inherit the link structure of their parent nodes. The ILDT model may be viewed as a directed analogue of the ILT model for undirected graphs introduced in \cite{ilt}. We investigate network science and graph theoretical properties of ILDT digraphs. We prove that the ILDT model exhibits a densification power law, so that the digraphs generated by the models densify over time. The number of directed triads are investigated, and counts are given of the number of directed 3-cycles and transitive $3$ -cycles. A higher number of transitive 3-cycles are generated by the ILDT model, as found in real-world, on-line social networks. In many instances of the chosen initial digraph, the model eventually generates graphs with Hamiltonian directed cycles. We finish with a discussion of the eigenvalues of the adjacency matrices of ILDT directed graphs, and provide further directions.

preprint2018arXiv

Circular Flows in Planar Graphs

For integers $a\ge 2b>0$ , a \emph{circular $a/b$ -flow} is a flow that takes values from $\{\pm b, \pm(b+1), \dots, \pm(a-b)\}$ . The Planar Circular Flow Conjecture states that every $2k$ -edge-connected planar graph admits a circular $(2+\frac{2}{k})$ -flow. The cases $k=1$ and $k=2$ are equivalent to the Four Color Theorem and Grötzsch's 3-Color Theorem. For $k\ge 3$ , the conjecture remains open. Here we make progress when $k=4$ and $k=6$ . We prove that (i) {\em every 10-edge-connected planar graph admits a circular 5/2-flow} and (ii) {\em every 16-edge-connected planar graph admits a circular 7/3-flow.} The dual version of statement (i) on circular coloring was previously proved by Dvořák and Postle (Combinatorica 2017), but our proof has the advantages of being much shorter and avoiding the use of computers for case-checking. Further, it has new implications for antisymmetric flows. Statement (ii) is especially interesting because the counterexamples to Jaeger's original Circular Flow Conjecture are 12-edge-connected nonplanar graphs that admit no circular 7/3-flow. Thus, the planarity hypothesis of (ii) is essential.

preprint2016arXiv

Planar Graphs have Independence Ratio at least 3/13

The 4 Color Theorem (4CT) implies that every $n$ -vertex planar graph has an independent set of size at least $\frac{n}4$ ; this is best possible, as shown by the disjoint union of many copies of $K_4$ . In 1968, Erdős asked whether this bound on independence number could be proved more easily than the full 4CT. In 1976 Albertson showed (independently of the 4CT) that every $n$ -vertex planar graph has an independent set of size at least $\frac{2n}9$ . Until now, this remained the best bound independent of the 4CT. Our main result improves this bound to $\frac{3n}{13}$ .

preprint2015arXiv

Edge-coloring via fixable subgraphs

Many graph coloring proofs proceed by showing that a minimal counterexample to the theorem being proved cannot contain certain configurations, and then showing that each graph under consideration contains at least one such configuration; these configurations are called \emph{reducible} for that theorem. (A \emph{configuration} is a subgraph $H$ , along with specified degrees $d_G(v)$ in the original graph $G$ for each vertex of $H$ .) We give a general framework for showing that configurations are reducible for edge-coloring. A particular form of reducibility, called \emph{fixability}, can be considered without reference to a containing graph. This has two key benefits: (i) we can now formulate necessary conditions for fixability, and (ii) the problem of fixability is easy for a computer to solve. The necessary condition of \emph{superabundance} is sufficient for multistars and we conjecture that it is sufficient for trees as well, which would generalize the powerful technique of Tashkinov trees. Via computer, we can generate thousands of reducible configurations, but we have short proofs for only a small fraction of these. The computer can write \LaTeX\ code for its proofs, but they are only marginally enlightening and can run thousands of pages long. We give examples of how to use some of these reducible configurations to prove conjectures on edge-coloring for small maximum degree. Our aims in writing this paper are (i) to provide a common context for a variety of reducible configurations for edge-coloring and (ii) to spur development of methods for humans to understand what the computer already knows.

preprint2015arXiv

List-coloring the Square of a Subcubic Graph

The {\em square} $G^2$ of a graph $G$ is the graph with the same vertex set as $G$ and with two vertices adjacent if their distance in $G$ is at most 2. Thomassen showed that every planar graph $G$ with maximum degree $Δ(G)=3$ satisfies $χ(G^2)\leq 7$ . Kostochka and Woodall conjectured that for every graph, the list-chromatic number of $G^2$ equals the chromatic number of $G^2$ , that is $χ_l(G^2)=χ(G^2)$ for all $G$ . If true, this conjecture (together with Thomassen's result) implies that every planar graph $G$ with $Δ(G)=3$ satisfies $χ_l(G^2)\leq 7$ . We prove that every connected graph (not necessarily planar) with $Δ(G)=3$ other than the Petersen graph satisfies $χ_l(G^2)\leq 8$ (and this is best possible). In addition, we show that if $G$ is a planar graph with $Δ(G)=3$ and girth $g(G)\geq 7$ , then $χ_l(G^2)\leq 7$ . Dvořák, Škrekovski, and Tancer showed that if $G$ is a planar graph with $Δ(G) = 3$ and girth $g(G) \geq 10$ , then $χ_l(G^2)\leq 6$ . We improve the girth bound to show that if $G$ is a planar graph with $Δ(G)=3$ and $g(G) \geq 9$ , then $χ_l(G^2) \leq 6$ . All of our proofs can be easily translated into linear-time coloring algorithms.

preprint2014arXiv

A note on coloring vertex-transitive graphs

We prove bounds on the chromatic number $χ$ of a vertex-transitive graph in terms of its clique number $ω$ and maximum degree $Δ$ . We conjecture that every vertex-transitive graph satisfies $χ\le \max \left\{ω, \left\lceil\frac{5Δ+ 3}{6}\right\rceil\right\}$ and we prove results supporting this conjecture. Finally, for vertex-transitive graphs with $Δ\ge 13$ we prove the Borodin-Kostochka conjecture, i.e., $χ\le\max\{ω,Δ-1\}$ .

preprint2013arXiv

1,2,3-Conjecture and 1,2-Conjecture for Sparse Graphs

We apply the Discharging Method to prove the 1,2,3-Conjecture and the 1,2-Conjecture for graphs with maximum average degree less than 8/3. Stronger results on these conjectures have been proved, but this is the first application of discharging to them, and the structure theorems and reducibility results are of independent interest.

preprint2013arXiv

Choice number of complete multipartite graphs $K_{33,2(k-5),12}$ and $K_{4,32,2(k-6),13}$

A graph $G$ is called \emph{chromatic-choosable} if its choice number is equal to its chromatic number, namely $Ch(G)=χ(G)$ . Ohba has conjectured that every graph $G$ satisfying $|V(G)|\leq 2χ(G)+1$ is chromatic-choosable. Since each $k$ -chromatic graph is a subgraph of a complete $k$ -partite graph, we see that Ohba's conjecture is true if and only if it is true for every complete multipartite graph. However, the only complete multipartite graphs for which Ohba's conjecture has been verified are: $K_{3*2,2*(k-3),1}$ , $K_{3,2*(k-1)}$ , $K_{s+3,2*(k-s-1),1*s}$ , $K_{4,3,2*(k-4),1*2}$ , and $K_{5,3,2*(k-5),1*3}$ . In this paper, we show that Ohba's conjecture is true for two new classes of complete multipartite graphs: graphs with three parts of size 3 and graphs with one part of size 4 and two parts of size 3. Namely, we prove that $Ch(K_{3*3,2*(k-5),1*2})=k$ and $Ch(K_{4,3*2,2*(k-6),1*3})=k$ (for $k\geq 5$ and $k\geq 6$ , respectively).

preprint2013arXiv

Choosability of the square of a planar graph with maximum degree four

We study squares of planar graphs with the aim to determine their list chromatic number. We present new upper bounds for the square of a planar graph with maximum degree $Δ\leq 4$ . In particular $G^2$ is 5-, 6-, 7-, 8-, 12-, 14-choosable if the girth of $G$ is at least 16, 11, 9, 7, 5, 3 respectively. In fact we prove more general results, in terms of maximum average degree, that imply the results above.

preprint2013arXiv

Multigraphs with $Δ\ge 3$ are Totally- $(2Δ-1)$ -choosable

The \emph{total graph} $T(G)$ of a multigraph $G$ has as its vertices the set of edges and vertices of $G$ and has an edge between two vertices if their corresponding elements are either adjacent or incident in $G$ . We show that if $G$ has maximum degree $Δ(G)$ , then $T(G)$ is $(2Δ(G)-1)$ -choosable. We give a linear-time algorithm that produces such a coloring. The best previous general upper bound for $Δ(G) > 3$ was $\floor{\frac32Δ(G)+2}$, by Borodin et al. When $Δ(G)=4$ , our algorithm gives a better upper bound. When $Δ(G)\in\{3,5,6\}$ , our algorithm matches the best known bound. However, because our algorithm is significantly simpler, it runs in linear time (unlike the algorithm of Borodin et al.).

preprint2013arXiv

On the Boundedness of Positive Solutions of the Reciprocal Max-Type Difference Equation $x_{n}=\max\left\{\frac{A^{1}_{n-1}}{x_{n-1}}, \frac{A^{2}_{n-1}}{x_{n-2}}, \ldots, \frac{A^{t}_{n-1}}{x_{n-t}}\right\}$ with Periodic Parameters

We investigate the boundedness of positive solutions of the reciprocal max-type difference equation $x_{n}=\max\left\{\frac{A_{n-1}^{1}}{x_{n-1}}, \frac{A_{n-1}^{2}}{x_{n-2}}, \ldots, \frac{A_{n-1}^{t}}{x_{n-t}}\right\}, \ \ n=1, 2, \ldots,$ where, for each value of $i$ , the sequence $\{A_{n}^{i}\}_{n=0}^{\infty}$ of positive numbers is periodic with period $p_{i}$ . We give both sufficient conditions on the $p_{i}$ 's for the boundedness of all solutions and sufficient conditions for all solutions to be unbounded. This work essentially complements the work by Biddell and Franke, who showed that as long as every positive solution of our equation is \emph{bounded}, then every positive solution is eventually periodic, thereby leaving open the question as to when solutions are bounded.

preprint2013arXiv

Regular graphs of odd degree are antimagic

An antimagic labeling of a graph $G$ with $m$ edges is a bijection from $E(G)$ to $\{1,2,\ldots,m\}$ such that for all vertices $u$ and $v$ , the sum of labels on edges incident to $u$ differs from that for edges incident to $v$ . Hartsfield and Ringel conjectured that every connected graph other than the single edge $K_2$ has an antimagic labeling. We prove this conjecture for regular graphs of odd degree.

preprint2013arXiv

Sufficient sparseness conditions for G^2 to be (Δ+1)-choosable, when Δ\ge5

We determine the list chromatic number of the square of a graph $\chil(G^2)$ in terms of its maximum degree $Δ$ when its maximum average degree, denoted $\mad(G)$, is sufficiently small. For $Δ\ge 6$ , if $\mad(G)<2+\frac{4Δ-8}{5Δ+2}$, then $\chil(G^2)=Δ+1$. In particular, if $G$ is planar with girth $g\ge 7+\frac{12}{Δ-2}$ , then $\chil(G^2)=Δ+1$. Under the same conditions, $\chil^i(G)=Δ$, where $\chil^i$ is the list injective chromatic number.

preprint2012arXiv

Coloring claw-free graphs with Δ-1 colors

We prove that every claw-free graph $G$ that doesn't contain a clique on $Δ(G) \geq 9$ vertices can be $Δ(G) - 1$ colored.

preprint2012arXiv

Game matching number of graphs

We study a competitive optimization version of $α'(G)$ , the maximum size of a matching in a graph $G$ . Players alternate adding edges of $G$ to a matching until it becomes a maximal matching. One player (Max) wants that matching to be large; the other (Min) wants it to be small. The resulting sizes under optimal play when Max or Min starts are denoted $\Max(G)$ and $\Min(G)$, respectively. We show that always $|\Max(G)-\Min(G)|\le 1$. We obtain a sufficient condition for $\Max(G)=α'(G)$ that is preserved under cartesian product. In general, $\Max(G)\ge \frac23α'(G)$, with equality for many split graphs, while $\Max(G)\ge\frac34α'(G)$ when $G$ is a forest. Whenever $G$ is a 3-regular $n$ -vertex connected graph, $\Max(G) \ge n/3$, and there are such examples with $\Max(G)\le 7n/18$. For an $n$ -vertex path or cycle, the answer is roughly $n/7$ .

preprint2012arXiv

Hamiltonicity in connected regular graphs

In 1980, Jackson proved that every 2-connected $k$ -regular graph with at most $3k$ vertices is Hamiltonian. This result has been extended in several papers. In this note, we determine the minimum number of vertices in a connected $k$ -regular graph that is not Hamiltonian, and we also solve the analogous problem for Hamiltonian paths. Further, we characterize the smallest connected $k$ -regular graphs without a Hamiltonian cycle.

preprint2012arXiv

Revolutionaries and spies: Spy-good and spy-bad graphs

We study a game on a graph $G$ played by $r$ {\it revolutionaries} and $s$ {\it spies}. Initially, revolutionaries and then spies occupy vertices. In each subsequent round, each revolutionary may move to a neighboring vertex or not move, and then each spy has the same option. The revolutionaries win if $m$ of them meet at some vertex having no spy (at the end of a round); the spies win if they can avoid this forever. Let $σ(G,m,r)$ denote the minimum number of spies needed to win. To avoid degenerate cases, assume $|V(G)|\ge r-m+1\ge\floor{r/m}\ge 1$. The easy bounds are then $\floor{r/m}\le σ(G,m,r)\le r-m+1$. We prove that the lower bound is sharp when $G$ has a rooted spanning tree $T$ such that every edge of $G$ not in $T$ joins two vertices having the same parent in $T$ . As a consequence, $σ(G,m,r)\leγ(G)\floor{r/m}$, where $γ(G)$ is the domination number; this bound is nearly sharp when $γ(G)\le m$ . For the random graph with constant edge-probability $p$ , we obtain constants $c$ and $c'$ (depending on $m$ and $p$ ) such that $σ(G,m,r)$ is near the trivial upper bound when $r<c\ln n$ and at most $c'$ times the trivial lower bound when $r>c'\ln n$ . For the hypercube $Q_d$ with $d\ge r$ , we have $σ(G,m,r)=r-m+1$ when $m=2$ , and for $m\ge 3$ at least $r-39m$ spies are needed. For complete $k$ -partite graphs with partite sets of size at least $2r$ , the leading term in $σ(G,m,r)$ is approximately $\frac{k}{k-1}\frac{r}{m}$ when $k\ge m$ . For $k=2$ , we have $σ(G,2,r)=\bigl\lceil{\frac{\floor{7r/2}-3}5}\bigr\rceil$ and $σ(G,3,r)=\floor{r/2}$, and in general $\frac{3r}{2m}-3\le σ(G,m,r)\le\frac{(1+1/\sqrt3)r}{m}$ .

preprint2011arXiv

Chain-making games in grid-like posets

We study the Maker-Breaker game on the hypergraph of chains of fixed size in a poset. In a product of chains, the maximum size of a chain that Maker can guarantee building is $k-\lfloor r/2\rfloor$ , where $k$ is the maximum size of a chain in the product, and $r$ is the maximum size of a factor chain. We also study a variant in which Maker must follow the chain in order, called the {\it Walker-Blocker game}. In the poset consisting of the bottom $k$ levels of the product of $d$ arbitrarily long chains, Walker can guarantee a chain that hits all levels if $d\ge14$ ; this result uses a solution to Conway's Angel-Devil game. When d=2, the maximum that Walker can guarantee is only 2/3 of the levels, and 2/3 is asymptotically achievable in the product of two equal chains.

preprint2011arXiv

List colorings of $K_5$ -minor-free graphs with special list assignments

A {\it list assignment} $L$ of a graph $G$ is a function that assigns a set (list) $L(v)$ of colors to every vertex $v$ of $G$ . Graph $G$ is called {\it $L$ -list colorable} if it admits a vertex coloring $ϕ$ such that $ϕ(v)\in L(v)$ for all $v\in V(G)$ and $ϕ(v)\not=ϕ(w)$ for all $vw\in E(G)$ . The following question was raised by Bruce Richter. Let $G$ be a planar, 3-connected graph that is not a complete graph. Denoting by $d(v)$ the degree of vertex $v$ , is $G$ $L$ -list colorable for every list assignment $L$ with $|L(v)|=\min \{d(v), 6\}$ for all $v\in V(G)$ ? More generally, we ask for which pairs $(r,k)$ the following question has an affirmative answer. Let $r$ and $k$ be integers and let $G$ be a $K_5$ -minor-free $r$ -connected graph that is not a Gallai tree (i.e., at least one block of $G$ is neither a complete graph nor an odd cycle). Is $G$ $L$ -list colorable for every list assignment $L$ with $|L(v)|=\min\{d(v),k\}$ for all $v\in V(G)$ ? We investigate this question by considering the components of $G[S_k]$ , where $S_k:=\{v\in V(G) | d(v)<k\}$ is the set of vertices with small degree in $G$ . We are especially interested in the minimum distance $d(S_k)$ in $G$ between the components of $G[S_k]$ .

preprint2011arXiv

New results in $t$ -tone coloring of graphs

A $t$ -tone $k$ -coloring of $G$ assigns to each vertex of $G$ a set of $t$ colors from $\{1,..., k\}$ so that vertices at distance $d$ share fewer than $d$ common colors. The {\it $t$ -tone chromatic number} of $G$ , denoted $τ_t(G)$ , is the minimum $k$ such that $G$ has a $t$ -tone $k$ -coloring. Bickle and Phillips showed that always $τ_2(G) \le [Δ(G)]^2 + Δ(G)$ , but conjectured that in fact $τ_2(G) \le 2Δ(G) + 2$ ; we confirm this conjecture when $Δ(G) \le 3$ and also show that always $τ_2(G) \le \ceil{(2 + \sqrt{2})Δ(G)}$. For general $t$ we prove that $τ_t(G) \le (t^2+t)Δ(G)$ . Finally, for each $t\ge 2$ we show that there exist constants $c_1$ and $c_2$ such that for every tree $T$ we have $c_1 \sqrt{Δ(T)} \le τ_t(T) \le c_2\sqrt{Δ(T)}$ .

preprint2011arXiv

Revolutionaries and spies on trees and unicyclic graphs

A team of $r$ {\it revolutionaries} and a team of $s$ {\it spies} play a game on a graph $G$ . Initially, revolutionaries and then spies take positions at vertices. In each subsequent round, each revolutionary may move to an adjacent vertex or not move, and then each spy has the same option. The revolutionaries want to hold an {\it unguarded meeting}, meaning $m$ revolutionaries at some vertex having no spy at the end of a round. To prevent this forever, trivially at least $\min\{|V(G)|,\FL{r/m}\}$ spies are needed. When $G$ is a tree, this many spies suffices. When $G$ is a unicyclic graph, $\min\{|V(G)|,\CL{r/m}\}$ spies suffice, and we characterize those unicyclic graphs where $\FL{r/m}+1$ spies are needed. \def\FL#1{\lfloor #1 \rfloor} \def\CL#1{\lceil #1 \rceil}

preprint2010arXiv

A New Lower Bound on the Density of Vertex Identifying Codes for the Infinite Hexagonal Grid

Given a graph $G$ , an identifying code $C \subseteq V(G)$ is a vertex set such that for any two distinct vertices $v_1,v_2\in V(G)$ , the sets $N[v_1]\cap C$ and $N[v_2]\cap C$ are distinct and nonempty (here $N[v]$ denotes a vertex $v$ and its neighbors). We study the case when $G$ is the infinite hexagonal grid $H$ . Cohen et.al. constructed two identifying codes for $H$ with density $3/7$ and proved that any identifying code for $H$ must have density at least $16/39\approx0.410256$ . Both their upper and lower bounds were best known until now. Here we prove a lower bound of $12/29\approx0.413793$ .

preprint2010arXiv

Crossings, colorings, and cliques

Albertson conjectured that if graph $G$ has chromatic number $r$ , then the crossing number of $G$ is at least that of the complete graph $K_r$ . This conjecture in the case $r=5$ is equivalent to the four color theorem. It was verified for $r=6$ by Oporowski and Zhao. In this paper, we prove the conjecture for $7 \leq r \leq 12$ using results of Dirac; Gallai; and Kostochka and Stiebitz that give lower bounds on the number of edges in critical graphs, together with lower bounds by Pach et.al. on the crossing number of graphs in terms of the number of edges and vertices.

preprint2010arXiv

Injective colorings of graphs with low average degree

Let $\mad(G)$ denote the maximum average degree (over all subgraphs) of $G$ and let $χ_i(G)$ denote the injective chromatic number of $G$ . We prove that if $Δ\geq 4$ and $\mad(G)<\frac{14}5$, then $χ_i(G)\leqΔ+2$ . When $Δ=3$ , we show that $\mad(G)<\frac{36}{13}$ implies $χ_i(G)\le 5$ . In contrast, we give a graph $G$ with $Δ=3$ , $\mad(G)=\frac{36}{13}$, and $χ_i(G)=6$ .

preprint2010arXiv

Injective colorings of sparse graphs

Let $mad(G)$ denote the maximum average degree (over all subgraphs) of $G$ and let $χ_i(G)$ denote the injective chromatic number of $G$ . We prove that if $mad(G) \leq 5/2$ , then $χ_i(G)\leqΔ(G) + 1$ ; and if $mad(G) < 42/19$ , then $χ_i(G)=Δ(G)$ . Suppose that $G$ is a planar graph with girth $g(G)$ and $Δ(G)\geq 4$ . We prove that if $g(G)\geq 9$ , then $χ_i(G)\leqΔ(G)+1$ ; similarly, if $g(G)\geq 13$ , then $χ_i(G)=Δ(G)$ .

preprint2010arXiv

Linear Choosability of Sparse Graphs

We study the linear list chromatic number, denoted $\lcl(G)$, of sparse graphs. The maximum average degree of a graph $G$ , denoted $\mad(G)$, is the maximum of the average degrees of all subgraphs of $G$ . It is clear that any graph $G$ with maximum degree $Δ(G)$ satisfies $\lcl(G)\ge \ceil{Δ(G)/2}+1$. In this paper, we prove the following results: (1) if $\mad(G)<12/5$ and $Δ(G)\ge 3$ , then $\lcl(G)=\ceil{Δ(G)/2}+1$, and we give an infinite family of examples to show that this result is best possible; (2) if $\mad(G)<3$ and $Δ(G)\ge 9$ , then $\lcl(G)\le\ceil{Δ(G)/2}+2$, and we give an infinite family of examples to show that the bound on $\mad(G)$ cannot be increased in general; (3) if $G$ is planar and has girth at least 5, then $\lcl(G)\le\ceil{Δ(G)/2}+4$.

preprint2010arXiv

Overlap Number of Graphs

An {\it overlap representation} of a graph $G$ assigns sets to vertices so that vertices are adjacent if and only if their assigned sets intersect with neither containing the other. The {\it overlap number} $\ol(G)$ (introduced by Rosgen) is the minimum size of the union of the sets in such a representation. We prove the following: (1) An optimal overlap representation of a tree can be produced in linear time, and its size is the number of vertices in the largest subtree in which the neighbor of any leaf has degree 2. (2) If $δ(G)\ge 2$ and $G\ne K_3$ , then $\ol(G)\le |E(G)|-1$, with equality when $G$ is connected and triangle-free and has no star-cutset. (3) If $G$ is an $n$ -vertex plane graph with $n\ge5$ , then $\ol(G)\le 2n-5$, with equality when every face has length 4 and there is no star-cutset. (4) If $G$ is an $n$ -vertex graph with $n\ge 14$ , then $\ol(G)\le \floor{n^2/4-n/2-1}$, and this is sharp (for even $n$ , equality holds when $G$ arises from $K_{n/2,n/2}$ by deleting a perfect matching).

preprint2008arXiv

Classes of 3-regular graphs that are (7, 2)-edge-choosable

A graph is (7, 2)-edge-choosable if, for every assignment of lists of size 7 to the edges, it is possible to choose two colors for each edge from its list so that no color is chosen for two incident edges. We show that every 3-edge-colorable graph is (7, 2)-edge-choosable and also that many non-3-edge-colorable 3-regular graphs are (7, 2)-edge-choosable.

preprint2008arXiv

Edge-choosability and total-choosability of planar graphs with no adjacent 3-cycles

Let $G$ be a planar graph with no two 3-cycles sharing an edge. We show that if $Δ(G)\geq 9$ , then $χ'_l(G) = Δ(G)$ and $χ''_l(G)=Δ(G)+1.$ We also show that if $Δ(G)\geq 6$ , then $χ'_l(G)\leqΔ(G)+1$ and if $Δ(G)\geq 7$ , then $χ''_l(G)\leqΔ(G)+2$ . All of these results extend to graphs in the projective plane and when $Δ(G)\geq 7$ the results also extend to graphs in the torus and Klein bottle. This second edge-choosability result improves on work of Wang and Lih and of Zhang and Wu. All of our results use the discharging method to prove structural lemmas about the existence of subgraphs with small degree-sum. For example, we prove that if $G$ is a planar graph with no two 3-cycles sharing an edge and with $Δ(G)\geq 7$ , then $G$ has an edge $uv$ with $d(u)\leq 4$ and $d(u)+d(v)\leq Δ(G)+2$ . All of our proofs yield linear-time algorithms that produce the desired colorings.

preprint2007arXiv

Antimagic labelings of regular bipartite graphs: An application of the Marriage Theorem

A labeling of a graph is a bijection from $E(G)$ to the set $\{1, 2,..., |E(G)|\}$ . A labeling is \textit{antimagic} if for any distinct vertices $u$ and $v$ , the sum of the labels on edges incident to $u$ is different from the sum of the labels on edges incident to $v$ . We say a graph is antimagic if it has an antimagic labeling. In 1990, Ringel conjectured that every connected graph other than $K_2$ is antimagic. In this paper, we show that every regular bipartite graph (with degree at least 2) is antimagic. Our technique relies heavily on the Marriage Theorem.

preprint2006arXiv

Nomadic Decompositions of Bidirected Complete Graphs

We use $K^*_n$ to denote the bidirected complete graph on $n$ vertices. A nomadic Hamiltonian decomposition of $K^*_n$ is a Hamiltonian decomposition, with the additional property that ``nomads'' walk along the Hamiltonian cycles (moving one vertex per time step) without colliding. A nomadic near-Hamiltonian decomposition is defined similarly, except that the cycles in the decomposition have length $n-1$ , rather than length $n$ . J.A. Bondy asked whether these decompositions of $K^*_n$ exist for all $n$ . We show that $K^*_n$ admits a nomadic near-Hamiltonian decomposition when $n\not\equiv 2\bmod 4$ .

Daniel W. Cranston

Research overview

Is this your work?

33 publications

In Most 6-regular Toroidal Graphs All 5-colorings are Kempe Equivalent

List-Recoloring of Sparse Graphs

The Iterated Local Directed Transitivity Model for Social Networks

Circular Flows in Planar Graphs

Planar Graphs have Independence Ratio at least 3/13

Edge-coloring via fixable subgraphs

List-coloring the Square of a Subcubic Graph

A note on coloring vertex-transitive graphs

1,2,3-Conjecture and 1,2-Conjecture for Sparse Graphs

Choice number of complete multipartite graphs $K_{33,2(k-5),12}$ and $K_{4,32,2(k-6),13}$

Choosability of the square of a planar graph with maximum degree four

Multigraphs with $Δ\ge 3$ are Totally- $(2Δ-1)$ -choosable

On the Boundedness of Positive Solutions of the Reciprocal Max-Type Difference Equation $x_{n}=\max\left\{\frac{A^{1}_{n-1}}{x_{n-1}}, \frac{A^{2}_{n-1}}{x_{n-2}}, \ldots, \frac{A^{t}_{n-1}}{x_{n-t}}\right\}$ with Periodic Parameters

Regular graphs of odd degree are antimagic

Sufficient sparseness conditions for G^2 to be (Δ+1)-choosable, when Δ\ge5

Coloring claw-free graphs with Δ-1 colors

Game matching number of graphs

Hamiltonicity in connected regular graphs

Revolutionaries and spies: Spy-good and spy-bad graphs

Chain-making games in grid-like posets

List colorings of $K_5$ -minor-free graphs with special list assignments

New results in $t$ -tone coloring of graphs

Revolutionaries and spies on trees and unicyclic graphs

A New Lower Bound on the Density of Vertex Identifying Codes for the Infinite Hexagonal Grid

Crossings, colorings, and cliques

Injective colorings of graphs with low average degree

Injective colorings of sparse graphs

Linear Choosability of Sparse Graphs

Overlap Number of Graphs

Classes of 3-regular graphs that are (7, 2)-edge-choosable

Edge-choosability and total-choosability of planar graphs with no adjacent 3-cycles

Antimagic labelings of regular bipartite graphs: An application of the Marriage Theorem

Nomadic Decompositions of Bidirected Complete Graphs

See the researcher in context

Building this map preview

Daniel W. Cranston

Research overview

Is this your work?

33 publications

In Most 6-regular Toroidal Graphs All 5-colorings are Kempe Equivalent

List-Recoloring of Sparse Graphs

The Iterated Local Directed Transitivity Model for Social Networks

Circular Flows in Planar Graphs

Planar Graphs have Independence Ratio at least 3/13

Edge-coloring via fixable subgraphs

List-coloring the Square of a Subcubic Graph

A note on coloring vertex-transitive graphs

1,2,3-Conjecture and 1,2-Conjecture for Sparse Graphs

Choice number of complete multipartite graphs K3∗3,2∗(k−5),1∗2K_{3*3,2*(k-5),1*2}K3∗3,2∗(k−5),1∗2​ and K4,3∗2,2∗(k−6),1∗3K_{4,3*2,2*(k-6),1*3}K4,3∗2,2∗(k−6),1∗3​

Choosability of the square of a planar graph with maximum degree four

Multigraphs with Δ≥3Δ\ge 3Δ≥3 are Totally-(2Δ−1)(2Δ-1)(2Δ−1)-choosable

Regular graphs of odd degree are antimagic

Sufficient sparseness conditions for G^2 to be (Δ+1)-choosable, when Δ\ge5

Coloring claw-free graphs with Δ-1 colors

Game matching number of graphs

Hamiltonicity in connected regular graphs

Revolutionaries and spies: Spy-good and spy-bad graphs

Chain-making games in grid-like posets

List colorings of K5K_5K5​-minor-free graphs with special list assignments

New results in ttt-tone coloring of graphs

Revolutionaries and spies on trees and unicyclic graphs

A New Lower Bound on the Density of Vertex Identifying Codes for the Infinite Hexagonal Grid

Crossings, colorings, and cliques

Injective colorings of graphs with low average degree

Injective colorings of sparse graphs

Linear Choosability of Sparse Graphs

Overlap Number of Graphs

Classes of 3-regular graphs that are (7, 2)-edge-choosable

Edge-choosability and total-choosability of planar graphs with no adjacent 3-cycles

Antimagic labelings of regular bipartite graphs: An application of the Marriage Theorem

Nomadic Decompositions of Bidirected Complete Graphs

See the researcher in context

Building this map preview

Choice number of complete multipartite graphs $K_{33,2(k-5),12}$ and $K_{4,32,2(k-6),13}$

Multigraphs with $Δ\ge 3$ are Totally- $(2Δ-1)$ -choosable

List colorings of $K_5$ -minor-free graphs with special list assignments

New results in $t$ -tone coloring of graphs