¡@

Chi-critical graph conjecture

¡@

A graph G is chi-critical if the deletion of any edge results in a graph with smaller chromatic number. G is vertex chi-critical if the deletion of any vertex results in a graph with smaller chromatic number.

Chi-critical graph conjecture 1  (Hajiabolhassan)           Suppose G is a (vertex) chi-critical graph. If chi_c(G) < chi(G), then chi_c =< chi(G) - 1/2.

Chi-critical graph conjecture 2       Suppose G is a (vertex) chi-critical graph. If chi_c(G) < chi(G), then for any vertex x of G, chi_c(G-x) = chi(G-x).

Chi-critical graph conjecture 3        Suppose G is a (vertex) chi-critical graph and chi(G) > 4.  Then there is a vertex x of G such that chi_c(G-x) = chi(G-x).

It is  known [Zhu92] that for any epsilon > 0, there are chi-critical graphs G for which chi_c(G) = chi(G) and G has a vertex x such that chi_c(G-x) < chi(G) - 2 + epsilon.  It is also known [HZ02] that if G is a chi-critical graph,  then for any edge e of G, chi_c(G-e) = chi(G-e). 

For circular chromatic number of induced subgraphs of a graph, the following result is proved in  [Zhu02]:

Theorem 1. There  is an infinite family of graphs G with the following properties:

          G is  vertex chi-critical;

          chi(G) = chi_c(G) = 4;

          For any vertex x of G,  chi_c(G-x) = 8/3.

This is why I have the condition chi(G) >  4  in Conjecture 3. 

For (vertex) chi-critical graphs G for which chi_c(G) < chi(G), nothing is known about their circular chromatic number, and nothing is known about chi(G-x) for vertices x of G.