Search

We describe an algorithm for generating all k-critical H-free graphs, based on a method of Hoang et al. (A graph G is k-critical H-free if G is H-free, k-chromatic, and every H-free proper subgraph of G is (k−1)-colorable). Using this algorithm, we prove that there are only finitely many 4-critical (P7,Ck)-free graphs, for both k=4 and k=5. We also show that there are only finitely many 4-critical (P8,C4)-free graphs. For each of these cases we also give the complete lists of critical graphs and vertex-critical graphs. These results generalize previous work by Hell and Huang, and yield certifying algorithms for the 3-colorability problem in the respective classes. In addition, we prove a number of characterizations for 4-critical H-free graphs when H is disconnected. Moreover, we prove that for every t, the class of 4-critical planar Pt-free graphs is finite. We also determine all 52 4-critical planar P7-free graphs. We also prove that every P11-free graph of girth at least five is 3-colorable, and show that this is best possible by determining the smallest 4-chromatic P12-free graph of girth at least five. Moreover, we show that every P14-free graph of girth at least six and every P17-free graph of girth at least seven is 3-colorable. This strengthens results of Golovach et al.

We consider graphs G with Δ=3 such that χ′(G)=4 and χ′(G−e)=3 for every edge e, so-called critical graphs. Jakobsen noted that the Petersen graph with a vertex deleted, P∗, is such a graph and has average degree only 83. He showed that every critical graph has average degree at least 83, and asked if P∗ is the only graph where equality holds. A result of Cariolaro and Cariolaro shows that this is true. We strengthen this average degree bound further. Our main result is that if G is a subcubic critical graph other than P∗, then G has average degree at least 4617≈2.706. This bound is best possible, as shown by the Hajos join of two copies of P∗.

A strong edge coloring of a graph is an assignment of colors to the edges of the graph such that for every color, the set of edges that are given that color form an induced matching in the graph. The strong chromatic index of a graph G, denoted by i¾?s'G, is the minimum number of colors needed in any strong edge coloring of G. A graph is said to be chordless if there is no cycle in the graph that has a chord. Faudree, Gyarfas, Schelp, and Tuza The Strong Chromatic Index of Graphs, Ars Combin 29B 1990, 205-211 considered a particular subclass of chordless graphs, namely, the class of graphs in which all the cycle lengths are multiples of four, and asked whether the strong chromatic index of these graphs can be bounded by a linear function of the maximum degree. Chang and Narayanan Strong Chromatic Index of 2-degenerate Graphs, J Graph Theory, 732 2013, 119-126 answered this question in the affirmative by proving that if G is a chordless graph with maximum degree Δ, then i¾?s'Gi¾?8Δ-6. We improve this result by showing that for every chordless graph G with maximum degree Δ, i¾?s'Gi¾?3Δ. This bound is tight up to an additive constant.

The local chromatic number is a coloring parameter defined as the minimum number of colors that should appear in the most colorful closed neighborhood of a vertex under any proper coloring of the graph. Its directed version is the same when we consider only outneighborhoods in a directed graph. For digraphs with all arcs being present in both directions the two values are obviously equal. Here, we consider oriented graphs. We show the existence of a graph where the directed local chromatic number of all oriented versions of the graph is strictly less than the local chromatic number of the underlying undirected graph. We show that for fractional versions the analogous problem has a different answer: there always exists an orientation for which the directed and undirected values coincide. We also determine the supremum of the possible ratios of these fractional parameters, which turns out to be e, the basis of the natural logarithm.

This article intends to study some functors from the category of graphs to itself such that, for any graph G, the circular chromatic number of is determined by that of G. In this regard, we investigate some coloring properties of graph powers. We show that provided that . As a consequence, we show that if , then . In particular, and has no subgraph with circular chromatic number equal to . This provides a negative answer to a question asked in (X. Zhu, Discrete Math, 229(1–3) (2001), 371–410). Moreover, we investigate the nth multichromatic number of subdivision graphs. Also, we present an upper bound for the fractional chromatic number of subdivision graphs. Precisely, we show that .

The star chromatic index χs′(G) of a graph G is the minimum number of colors needed to properly color the edges of the graph so that no path or cycle of length four is bi-colored. We obtain a near-linear upper bound in terms of the maximum degree Δ=Δ(G). Our best lower bound on χs′ in terms of Δ is 2Δ(1+o(1)) valid for complete graphs. We also consider the special case of cubic graphs, for which we show that the star chromatic index lies between 4 and 7 and characterize the graphs attaining the lower bound. The proofs involve a variety of notions from other branches of mathematics and may therefore be of certain independent interest.

A graph G with maximum degree Δ and edge chromatic number χ′(G)>Δ is edge-Δ-critical if χ′(G−e)=Δ for every edge e of G. It is proved here that the vertex independence number of an edge-Δ-critical graph of order n is less than **image**. For large Δ, this improves on the best bound previously known, which was roughly **image**; the bound conjectured by Vizing, which would be best possible, is **image**. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:98-103, 2011 © 2011 Wiley Periodicals, Inc.

We investigate the local chromatic number of shift graphs and prove that it is close to their chromatic number. This implies that the gap between the directed local chromatic number of an oriented graph and the local chromatic number of the underlying undirected graph can be arbitrarily large. We also investigate the minimum possible directed local chromatic number of oriented versions of ``topologically t-chromatic'' graphs. We show that this minimum for large enough t-chromatic Schrijver graphs and t-chromatic generalized Mycielski graphs of appropriate parameters is the upper integer part of t/4+1., Comment: 18 pages

In this article we give examples of a triangle-free graph on 22 vertices with chromatic number 5 and a K4-free graph on 11 vertices with chromatic number 5. We very briefly describe the computer searches demonstrating that these are the smallest possible such graphs. All 5-critical graphs on 9 vertices are exhibited. © 1995 John Wiley & Sons, Inc.

The analysis and synthesis of reliable large-scale networks typically involve a graph theoretic model. We give a survey of the graph theoretic notions which are relevant to the synthesis problem. It is shown how a number of unsolved graph extremal problems relate to the synthesis question.

Here we examine six definitions of criticality concerning the chromatic index (edge chromatic number) of a simple graph. Five of these turn out to be almost always almost equivalent. Some problems arise and some conjectures are posed.

In this expository paper we discuss the critical graph conjecture and its eventual disproof by M.K. Goldberg and others.