Search

Let $G$ be a graph and $k$ be a positive integer, and let $Kc(G, k)$ denote the number of Kempe equivalence classes for the $k$-colorings of $G$. In 2006, Mohar noted that $Kc(G, k) = 1$ if $G$ is bipartite. As a generalization, we show that $Kc(G, k) = 1$ if $G$ is formed from a bipartite graph by adding any number of edges less than $\binom{\lceil k/2\rceil}2+\binom{\lfloor k/2\rfloor}2$. We show that our result is tight (up to lower order terms) by constructing, for each $k \geq 8$, a graph $G$ formed from a bipartite graph by adding $(k^2+8k-45+1)/4$ edges such that $Kc(G, k) \geq 2$. This refutes a recent conjecture of Higashitani--Matsumoto., Comment: 7 pages, 2 figures

A \emph{coloring} of a graph $G$ is a map $f:V(G)\to \mathbb{Z}^+$ such that $f(v)\ne f(w)$ for all $vw\in E(G)$. A coloring $f$ is an \emph{odd-sum} coloring if $\sum_{w\in N[v]}f(w)$ is odd, for each vertex $v\in V(G)$. The \emph{odd-sum chromatic number} of a graph $G$, denoted $\chi_{os}(G)$, is the minimum number of colors used (that is, the minimum size of the range) in an odd-sum coloring of $G$. Caro, Petru\v{s}evski, and \v{S}krekovski showed, among other results, that $\chi_{os}(G)$ is well-defined for every finite graph $G$ and, in fact, $\chi_{os}(G)\le 2\chi(G)$. Thus, $\chi_{os}(G)\le 8$ for every planar graph $G$ (by the 4 Color Theorem), $\chi_{os}(G)\le 6$ for every triangle-free planar graph $G$ (by Gr\"{o}tzsch's Theorem), and $\chi_{os}(G)\le 4$ for every bipartite planar graph. Caro et al. asked, for every even $\Delta\ge 4$, whether there exists $g_{\Delta}$ such that if $G$ is planar with maximum degree $\Delta$ and girth at least $g_{\Delta}$ then $\chi_{os}(G)\le 5$. They also asked, for every even $\Delta\ge 4$, whether there exists $g_{\Delta}$ such that if $G$ is planar and bipartite with maximum degree $\Delta$ and girth at least $g_{\Delta}$ then $\chi_{os}(G)\le 3$. We answer both questions negatively. We also refute a conjecture they made, resolve one further problem they posed, and make progress on another., Comment: 8 pages, 6 figures

An $\alpha,\beta$-Kempe swap in a properly colored graph interchanges the colors on some component of the subgraph induced by colors $\alpha$ and $\beta$. Two $k$-colorings of a graph are $k$-Kempe equivalent if we can form one from the other by a sequence of Kempe swaps (never using more than $k$ colors). Las Vergnas and Meyniel showed that if a graph is $(k-1)$-degenerate, then each pair of its $k$-colorings are $k$-Kempe equivalent. Mohar conjectured the same conclusion for connected $k$-regular graphs. This was proved for $k=3$ by Feghali, Johnson, and Paulusma (with a single exception $K_2\square K_3$, also called the 3-prism) and for $k\ge 4$ by Bonamy, Bousquet, Feghali, and Johnson. In this paper we prove an analogous result for list-coloring. For a list-assignment $L$ and an $L$-coloring $\varphi$, a Kempe swap is called $L$-valid for $\varphi$ if performing the Kempe swap yields another $L$-coloring. Two $L$-colorings are called $L$-equivalent if we can form one from the other by a sequence of $L$-valid Kempe swaps. Let $G$ be a connected $k$-regular graph with $k\ge 3$. We prove that if $L$ is a $k$-assignment, then all $L$-colorings are $L$-equivalent (again with a single exception $K_2 \square K_3$). When $k\ge 4$, the proof is completely self-contained, so implies an alternate proof of the result of Bonamy et al. Our proofs rely on the following key lemma, which may be of independent interest. Let $H$ be a graph such that for every degree-assignment $L_H$ all $L_H$-colorings are $L_H$-equivalent. If $G$ is a connected graph that contains $H$ as an induced subgraph, then for every degree-assignment $L_G$ for $G$ all $L_G$-colorings are $L_G$-equivalent., Comment: 27 pages, 8 figures; second version extends the main result to cliques, which were previously excluded

The Borodin-Kostochka Conjecture states that for a graph $G$, if $��(G) \geq 9$ and $��(G) \leq ��(G)-1$, then $��(G)\leq��(G) -1$. We prove the Borodin-Kostochka Conjecture for $(P_5, \text{gem})$-free graphs, i.e., graphs with no induced $P_5$ and no induced $K_1\vee P_4$., 8 pages, 6 figures

For each integer k >= 2, we determine a sharp bound on mad(G) such that V(G) can be partitioned into sets I and F_k, where I is an independent set and G[F_k] is a forest in which each component has at most k vertices. For each k we construct an infinite family of examples showing our result is best possible. Our results imply that every planar graph G of girth at least 9 (resp. 8, 7) has a partition of V(G) into an independent set I and a set F such that G[F] is a forest with each component of order at most 3 (resp. 4, 6). Hendrey, Norin, and Wood asked for the largest function g(a,b) such that if mad(G) < g(a,b) then V(G) has a partition into sets A and B such that mad(G[A]) < a and mad(G[B]) < b. They specifically asked for the value of g(1,b), i.e., the case when A is an independent set. Previously, the only values known were g(1,4/3) and g(1,2). We find g(1,b) whenever 4/3 < b < 2., 21 pages, 9 figures and 2 tables; this version incorporates reviewer feedback; to appear in SIAM J. Discrete Math

A multigraph $G$ is near-bipartite if $V(G)$ can be partitioned as $I,F$ such that $I$ is an independent set and $F$ induces a forest. We prove that a multigraph $G$ is near-bipartite when $3|W|-2|E(G[W])|\ge -1$ for every $W\subseteq V(G)$, and $G$ contains no $K_4$ and no Moser spindle. We prove that a simple graph $G$ is near-bipartite when $8|W|-5|E(G[W])|\ge -4$ for every $W\subseteq V(G)$, and $G$ contains no subgraph from some finite family $\mathcal{H}$. We also construct infinite families to show that both results are best possible in a very sharp sense., Comment: 37 pages, 21 figures; incorporates reviewer feedback; to appear in SIAM J. Discrete Math

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.

An \emph{acyclic edge-coloring} of a graph $G$ is a proper edge-coloring of $G$ such that the subgraph induced by any two color classes is acyclic. The \emph{acyclic chromatic index}, $��'_a(G)$, is the smallest number of colors allowing an acyclic edge-coloring of $G$. Clearly $��'_a(G)\ge ��(G)$ for every graph $G$. Cohen, Havet, and M��ller conjectured that there exists a constant $M$ such that every planar graph with $��(G)\ge M$ has $��'_a(G)=��(G)$. We prove this conjecture., 15 pages, 8 figures; minor revisions to incorporate reviewer feedback; to appear in SIAM J. Discrete Math

We prove a conjecture of Dvo����k, Kr��l, Nejedl��, and ��krekovski that planar graphs of girth at least five are square $(��+2)$-colorable for large enough $��$. In fact, we prove the stronger statement that such graphs are square $(��+2)$-choosable and even square $(��+2)$-paintable., 22 pages, 7 figures; this version incorporates reviewer feedback: fixed and rewrote proof of Lemma 3.5, expanded Section 4; to appear in J. Combin. Theory Ser. B

We prove that if $G$ is a quasi-line graph with $��(G)>��(G)$ and $��(G)\ge 69$, then $��_{OL}(G)\le ��(G)-1$. Together with our previous work, this implies that if $G$ is a claw-free graph with $��(G)>��(G)$ and $��(G)\ge 69$, then $��_{\ell}(G)\le ��(G)-1$., 24 pages, 5 figures

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., Comment: 29 pages, 19 figures; same results as earlier version, but revised introduction

Cranston and Kim conjecture that if $G$ is a connected graph with maximum degree $��$ and $G$ is not a Moore Graph, then $��_l(G^2) \le ��^2-1$; here $��_l$ is the list chromatic number. We prove their conjecture; in fact, this upper bound holds even for online list chromatic number., 23 pages, 10 figures. In version 2, we add a conjecture and 2 figures to the introduction. Results are unchanged

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.)., 6 pages, 2 figures

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), 16 pages, 6 figures; incorporated reviewer feedback

Brooks' Theorem states that if a graph has $��\ge 3$ and $��\le ��$, then $��\le ��$. Borodin and Kostochka conjectured that if $��\ge 9$ and $��\le ��-1$, then $��\le ��-1$. We show that if $��\ge 13$ and $��\le ��-4$, then $��\le ��-1$. For a graph $G$, let $\mathcal{H}$ denote the subgraph of $G$ induced by vertices of degree $��$. We also show that if $��\le ��-1$ and $��(\mathcal{H})\le ��-6$, then $��\le ��-1$., 27 pages, 3 figures; added many more details in this version, as well as a discussion of algorithms; to appear in SIAM J. Discrete Math

Borodin and Kostochka conjectured that every graph $G$ with maximum degree $��\ge 9$ satisfies $��\le \max\{��, ��-1\}$. We carry out an in-depth study of minimum counterexamples to the Borodin-Kostochka conjecture. Our main tool is the identification of graph joins that are $f$-choosable, where $f(v) = d(v) - 1$ for each vertex $v$. Since such a join cannot be an induced subgraph of a vertex critical graph with $��= ��$, we have a wealth of structural information about minimum counterexamples to the Borodin-Kostochka conjecture. Our main result proves that certain conjectures that are prima facie weaker than the Borodin-Kostochka conjecture are in fact equivalent to it. One such equivalent conjecture is the following: Any graph with $��\ge ��= 9$ contains $K_3 * \bar{K_6}$ as a subgraph., compact version only proving the list coloring results needed for the conjecture equivalences; 26 pages, 6 figures; final version accepted for publication

We prove that every claw-free graph $G$ that doesn't contain a clique on $��(G) \geq 9$ vertices can be $��(G) - 1$ colored., 18 pages, 4 figures; moved list-coloring section earlier; added overview at end of Section 1 and start of Section 2

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 $\phi$ such that $\phi(v)\in L(v)$ for all $v\in V(G)$ and $\phi(v)\not=\phi(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), Comment: 14 pages, 2 figures, 2 tables

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., Comment: 9 pages