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/