Search

A simple graph G is overfull if jE(G)j > bjV (G)j=2c. By the pigeonhole principle, every overfull graph G has 0(G) > . The core of a graph, denoted G, is the subgraph induced by its vertices of degree . Vizing's adjacency lemma implies that if 0(G) >, then G contains cycles. Hilton and Zhao conjectured that if G is connected with 4 and G has maximum degree 2, then 0(G) > precisely when G is overfull. We prove this conjecture for the case = 4. [ABSTRACT FROM AUTHOR]

An 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 acyclic chromatic index, &#967';α (G), is the smallest number of colors allowing an acyclic edge-coloring of G. Clearly &#967';α(G) ≥ Δ(G) for every graph G. Cohen, Havet, and Müller conjectured that there exists a constant M such that every planar graph with Δ(G) ≥ M has χ'α (G) = Δ(G). We prove this conjecture. [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]

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]

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]