Search

Given a graph G possibly with multiple edges but no loops, denote by Δ the maximum degree, μ the multiplicity, χ ′ the chromatic index and χ f ′ the fractional chromatic index of G, respectively. It is known that Δ ≤ χ f ′ ≤ χ ′ ≤ Δ + μ , where the upper bound is a classic result of Vizing. While deciding the exact value of χ ′ is a classic NP-complete problem, the computing of χ f ′ is in polynomial time . In fact, it is shown that if χ f ′ > Δ then χ f ′ = max ⁡ | E ( H ) | ⌊ | V ( H ) | / 2 ⌋ , where the maximality is taken over all induced subgraphs H of G. Gupta (1967), Goldberg (1973), Andersen (1977), and Seymour (1979) conjectured that χ ′ = ⌈ χ f ′ ⌉ if χ ′ ≥ Δ + 2 , which is commonly referred as Goldberg's conjecture. It has been shown that Goldberg's conjecture is equivalent to the following conjecture of Jakobsen: For any positive integer m with m ≥ 3 , every graph G with χ ′ > m m − 1 Δ + m − 3 m − 1 satisfies χ ′ = ⌈ χ f ′ ⌉ . Jakobsen's conjecture has been verified for m up to 15 by various researchers in the last four decades. We use an extended form of a Tashkinov tree to show that it is true for m ≤ 23 . With the same technique, we show that if χ ′ ≥ Δ + Δ / 2 3 then χ ′ = ⌈ χ f ′ ⌉ . The previous best known result is for graphs with χ ′ > Δ + Δ / 2 obtained by Scheide, and by Chen, Yu and Zang, independently. Moreover, we showthat Goldberg's conjecture holds for graphs G with Δ ≤ 23 or | V ( G ) | ≤ 23 .

Dirac introduced the notion of a k-critical graph, a graph that is not ( k − 1 ) -colorable but whose every proper subgraph is ( k − 1 ) -colorable. Brook's Theorem states that every graph with maximum degree k is k -colorable unless it contains a subgraph isomorphic to K k + 1 or an odd cycle (for k = 2 ). Equivalently, for all k ≥ 4 , the only k -critical graph of maximum degree k − 1 is K k . A natural generalization of Brook's theorem is to consider the Ore-degree of a graph, which is the maximum of d ( u ) + d ( v ) over all u v ∈ E ( G ) . Kierstead and Kostochka proved that for all k ≥ 6 the only k -critical graph with Ore-degree at most 2 k − 1 is K k . Kostochka, Rabern and Stiebitz proved that the only 5-critical graphs with Ore-degree at most 9 are K 5 and a graph they called O 5 . A different generalization of Brook's theorem, motivated by Hajos' construction, is Ore's conjectured bound on the minimum density of a k -critical graph. Recently, Kostochka and Yancey proved Gallai's conjecture. Their proof for k ≥ 5 implies the above results on Ore-degree. However, the case for k = 4 remains open, which is the subject of this paper. Kostochka and Yancey's short but beautiful proof for the case k = 4 says that if G is a 4-critical graph, then | E ( G ) | ≥ ( 5 | V ( G ) | − 2 ) / 3 . We prove the following bound which is better when there exists a large independent set of degree three vertices: if G is a 4-critical graph G , then | E ( G ) | ≥ 1.6 | V ( G ) | + . 2 α ( D 3 ( G ) ) − . 6 , where D 3 ( G ) is the graph induced by the degree three vertices of G . As a corollary, we characterize the 4-critical graphs with Ore-degree at most seven as precisely the graphs of Ore-degree seven in the family of graphs obtained from K 4 and Ore compositions.

A graph is totally critical if it is Type 2, connected, and the removal of any edge reduces the total chromatic number. A good characterization of all totally critical graphs is unlikely as Sanchez-Arroyo showed that determining the total chromatic number of a graph is an NP-hard problem. In this paper we show that if the Conformability Conjecture is correct, then totally critical graphs of even order with maximum degree at least one half of their order are characterized by a simple equation involving the order, maximum degree, and deficiency of the graph and the edge independence number of the complement. We also show that if the maximum degree Δ of a non-conformable graph G of even order satisfies 12|V|⩽Δ⩽34|V|−1 then G is regular and has a simple structure.

We investigate the notion of the star chromatic number of a graph in conjunction with various other graph parameters, among them, clique number, girth, and independence number.

A graph is stability critical (α-critical) if the removal of any edge increases the stability number. We give an affirmative answer to a question raised by Chváktal, namely, that every connected, critical graph that is neither K2 nor an odd cycle contains an even subdivision of K4

Although the chromatic number of a graph is not known in general, attempts have been made to find good bounds for the number. Here we prove that a K1,3-free and a {(K2 ∪ K1) + K2}-free graph has chromatic number at most equal to its maximum clique size plus one.

A question of P. Erdos is solved by showing that certain graphs have chromatic number at most three. The proof proceeds by showing a conjecture of Erdos and Bollobas holds, namely, that under certain circumstances, a graph which contains an odd circuit must contain an odd circuit with diagonal.

We prove that K"@g"("G") is the only vertex critical graph G with @g(G)>=@D(G)>=6 and @w(H(G))=

A conjecture of Richter and Salazar about graphs that are critical for a fixed crossing number $k$ is that they have bounded bandwidth. A weaker well-known conjecture of Richter is that their maximum degree is bounded in terms of $k$. In this note we disprove these conjectures for every $k\ge 171$, by providing examples of $k$-crossing-critical graphs with arbitrarily large maximum degree.

The relation between the arc-chromatic number and the chromatic number of a symmetric digraph is given. Using the notion of arc-coloring some remarks concerning the chromatic number of a product of two graphs, or of a product of two digraphs, are proved.

An obvious lower bound on the chromatic number of a graph is the largest possible number of points in a complete subgraph. A sufficient condition is presented for these numbers to be equal. From this is derived a necessary and sufficient condition, believed to be new, for a graph to be n-colorable.