¡@
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.