Search

Abstract We prove a conjecture of Dvořák, Král, Nejedlý, and Škrekovski that planar graphs of girth at least five with maximum degree Δ 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. [ABSTRACT FROM AUTHOR]

A graph G is k-critical if G is not (k − 1)-colorable, but every proper subgraph of G is (k − 1)-colorable. A graph G is k-choosable if G has an L-coloring from every list assignment L with |L(v)|=k for all v, and a graph G is k-list-critical if G is not (k−1)-choosable, but every proper subgraph of G is (k−1)-choosable. The problem of determining the minimum number of edges in a k-critical graph with n vertices has been widely studied, starting with work of Gallai and culminating with the seminal results of Kostochka and Yancey, who essentially solved the problem. In this paper, we improve the best known lower bound on the number of edges in a k-list-critical graph. In fact, our result on k-list-critical graphs is derived from a lower bound on the number of edges in a graph with Alon-Tarsi number at least k. Our proof uses the discharging method, which makes it simpler and more modular than previous work in this area. [ABSTRACT FROM AUTHOR]

We consider graphs G with [ABSTRACT FROM AUTHOR]

Let Xℓ and XOL denote the list-chromatic number and online list-chromatic number. We prove that if G is a quasi-line graph with maximum degree greater than clique number, i.e., Δ(G) > ω(G), and Δ (G) ≥ 69, then its online list-chromatic number is less than its maximum degree, i.e., XOL(G) ≤ Δ(G) - 1. Together with our previous work, this implies that if G is a claw-free graph with Δ(G) > ω(G) and Δ(G) > 69, then its list-chromatic number is less than its maximum degree, i.e., Xℓ (G) ≤ Δ(G) - 1. This verifies the list-coloring analogue of a conjecture of Borodin and Kostochka for every claw-free graph G with Δ(G) ≥ 69. [ABSTRACT FROM AUTHOR]

We collect some of our favorite proofs of Brooks' Theorem, highlighting advantages and extensions of each. The proofs illustrate some of the major techniques in graph coloring, such as greedy coloring, Kempe chains, hitting sets, and the Kernel Lemma. We also discuss standard strengthenings of vertex coloring, such as list coloring, online list coloring, and Alon-Tarsi orientations, since analogs of Brooks' Theorem hold in each context. We conclude with two conjectures along the lines of Brooks' Theorem that are much stronger, the Borodin-Kostochka Conjecture and Reed's Conjecture. [ABSTRACT FROM AUTHOR]

Brooks’ theorem implies that if a graph has Δ ≥ 3 and χ > Δ, then ω = Δ+1. Borodin and Kostochka conjectured that if Δ ≥ 9 and χ ≥ Δ, then ω ≥ Δ. We show that if Δ ≥ 13 and χ ≥ Δ, then ω ≥ Δ−3. For a graph G, let H(G) denote the subgraph of G induced by vertices of degree Δ. We also show that if χ ≥ Δ, then ω ≥ Δ or ω(H(G)) ≥ Δ − 5. [ABSTRACT FROM AUTHOR]

An antimagic labeling of a graph G with m edges is a bijection from [ABSTRACT FROM AUTHOR]

Abstract: We determine the list chromatic number of the square of a graph in terms of its maximum degree when its maximum average degree, denoted , is sufficiently small. For , if , then . In particular, if is planar with girth , then . Under the same conditions, , where is the list injective chromatic number. [Copyright &y& Elsevier]

Abstract: We study a competitive optimization version of , the maximum size of a matching in a graph . Players alternate adding edges of to a matching until it becomes a maximal matching. One player (Max) wants the final 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 and , respectively. We show that always . We obtain a sufficient condition for . Always , with equality for many split graphs, while when is a forest. Whenever is a -regular -vertex connected graph, , and such graphs exist with . For an -vertex path or cycle, the value is roughly . [Copyright &y& Elsevier]

We prove that every claw-free graph G that does not contain a clique on Δ(G) ≥ 9 vertices can be Δ(G) -- 1 colored. [ABSTRACT FROM AUTHOR]

Abstract: We study a game on a graph played by revolutionaries and 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 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 denote the minimum number of spies needed to win. To avoid degenerate cases, assume . The easy bounds are then . We prove that the lower bound is sharp when has a rooted spanning tree such that every edge of not in joins two vertices having the same parent in . As a consequence, , where is the domination number; this bound is nearly sharp when . For the random graph with constant edge-probability , we obtain constants and (depending on and ) such that is near the trivial upper bound when and at most times the trivial lower bound when . For the hypercube with , we have when , and for at least spies are needed. For complete -partite graphs with partite sets of size at least , the leading term in is approximately when . For , we have and , and in general . [Copyright &y& Elsevier]

Abstract: A linear coloring is a proper coloring such that each pair of color classes induces a union of disjoint paths. We study the linear list chromatic number, denoted , of sparse graphs. The maximum average degree of a graph , denoted , is the maximum of the average degrees of all subgraphs of . It is clear that any graph with maximum degree satisfies . In this paper, we prove the following results: (1) if and , then , and we give an infinite family of examples to show that this result is best possible; (2) if and , then , and we give an infinite family of examples to show that the bound on cannot be increased in general; (3) if is planar and has girth at least 5, then . [Copyright &y& Elsevier]

Abstract: Let denote the maximum average degree (over all subgraphs) of and let denote the injective chromatic number of . We prove that if , then ; and if , then . Suppose that is a planar graph with girth and . We prove that if , then ; similarly, if , then . [ABSTRACT FROM AUTHOR]

A graph is (7, 2)-edge-choosable if, for every assignment of lists of size 7 to the edges, it is possible to choose 2 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. [ABSTRACT FROM AUTHOR]

Let G be a planar graph with no two 3-cycles sharing an edge. We show that if Δ(G) ≥ 9, then χι′(G) = Δ(G) and χι″(G) = Δ(G)+1: We also show that if Δ(G) ≥ 6, then χι′(G) ≤ Δ(G) + 1 and if Δ(G) ≥ 7, then χι″(G) ≤ Δ(G) + 2. All of these results extend to graphs in the projective plane and when Δ(G) ≥ 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) ≥ 7, then G has an edge uv with d(u) ≤ 4 and d(u) + d(v) ≥ Δ(G) + 2. All of our proofs yield linear-time algorithms that produce the desired colorings. [ABSTRACT FROM AUTHOR]

Abstract: We use to denote the bidirected complete graph on n vertices. A nomadic Hamiltonian decomposition of 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 , rather than length n. Bondy asked whether these decompositions of exist for all n. We show that admits a nomadic near-Hamiltonian decomposition when . [Copyright &y& Elsevier]

The 1, 2, 3-Conjecture states that the edges of a graph without isolated edges can be labeled from {1,2,3} so that the sums of labels at adjacent vertices are distinct. The 1, 2-Conjecture states that if vertices also receive labels and the vertex label is added to the sum of its incident edge labels, then adjacent vertices can be distinguished using only {1, 2}. We show that various configurations cannot occur in minimal counterexamples to these conjectures. Discharging then confirms the conjectures for graphs with maximum average degree less than 8/3. The conjectures are already confirmed for larger families, but the structure theorems and reducibility results are of independent interest. [ABSTRACT FROM AUTHOR]

Abstract: A graph is called chromatic-choosable if its choice number is equal to its chromatic number, namely . Ohba has conjectured that every graph satisfying is chromatic-choosable. Since each -chromatic graph is a subgraph of a complete -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: , , , , and . 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 and (for and , respectively). [Copyright &y& Elsevier]