Geodesic
On a question of Dirac on critical and vertex critical graphs
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 9 (2012), pp. 156-160.

Voir la notice de l'article provenant de la source Math-Net.Ru

We give a construction which for any $N$ provides a graph on $n>N$ vertices which is vertex-critical with respect to being $4$-chromatic, has at least $cn^2$ edges that are non-critical (i.e., the removal of any one does not change the chromaticity) and has at most $Cn$ critical edges for some fixed positive constants $c$ and $C$. Thus for any $\varepsilon>0$ we get $4$-vertex-critical graphs in which less than an $\varepsilon$-proportion of the edges are non-critical.
Keywords: critical graph, vertex-criticality, critical edge, Dirac problem. 
@article{SEMR_2012_9_a19,
     author = {Tommy Jensen and Mark Siggers},
     title = {On a question of {Dirac} on critical and vertex critical graphs},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {156--160},
     publisher = {mathdoc},
     volume = {9},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2012_9_a19/}
}
TY  - JOUR
AU  - Tommy Jensen
AU  - Mark Siggers
TI  - On a question of Dirac on critical and vertex critical graphs
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2012
SP  - 156
EP  - 160
VL  - 9
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2012_9_a19/
LA  - en
ID  - SEMR_2012_9_a19
ER  - 
%0 Journal Article
%A Tommy Jensen
%A Mark Siggers
%T On a question of Dirac on critical and vertex critical graphs
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2012
%P 156-160
%V 9
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2012_9_a19/
%G en
%F SEMR_2012_9_a19
Tommy Jensen; Mark Siggers. On a question of Dirac on critical and vertex critical graphs. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 9 (2012), pp. 156-160. http://geodesic.mathdoc.fr/item/SEMR_2012_9_a19/

[1] J.I. Brown, “A vertex critical graph without critical edges”, Discrete Math., 102 (1992), 99–102 | DOI | MR | Zbl

[2] P. Erdős, “On some aspects of my work with Gabriel Dirac”, Graph Theory in Memory of G.A. Dirac, Annals of Discrete Mathematics, 41, North-Holland 1989, 111–116 | MR

[3] T.R. Jensen, “Dense critical and vertex-critical graphs”, Discrete Math., 258 (2002), 63–84 | DOI | MR | Zbl

[4] T.R. Jensen and B. Toft, “Problem 5.14”, Graph Coloring Problems, Wiley, 1995, 105–106

[5] J.J. Lattanzio, “A note on a conjecture of Dirac”, Discrete Math., 258 (2002), 323–330 | DOI | MR | Zbl