TY - JOUR
T1 - On almost (k - 1) -degenerate (k + 1) -chromatic graphs and hypergraphs
AU - Kostochka, Alexandr V.
N1 - Funding Information:
The author was supported by NSF grant DMS-0965587 and by grant 09-01-00244 of the Russian Foundation for Basic Research and the Ministry of Education and Science of the Russian Federation (Contract No. 14.740.11.0868 ).
PY - 2013
Y1 - 2013
N2 - Recall that a (hyper)graph is d-degenerate if each of its nonempty subgraphs has a vertex of degree at most d. Every d-degenerate (hyper)graph is (easily) (d+1)-colorable. A (hyper)graph is almost d-degenerate if it is not d-degenerate, but each of its proper subgraphs is d-degenerate. In particular, if G is almost (k-1)-degenerate, then after deleting any edge it is k-colorable. For k≥2, we study properties of almost (k-1)-degenerate (hyper)graphs that are not k-colorable. By definition, each such (hyper)graph is (k+1)-critical.
AB - Recall that a (hyper)graph is d-degenerate if each of its nonempty subgraphs has a vertex of degree at most d. Every d-degenerate (hyper)graph is (easily) (d+1)-colorable. A (hyper)graph is almost d-degenerate if it is not d-degenerate, but each of its proper subgraphs is d-degenerate. In particular, if G is almost (k-1)-degenerate, then after deleting any edge it is k-colorable. For k≥2, we study properties of almost (k-1)-degenerate (hyper)graphs that are not k-colorable. By definition, each such (hyper)graph is (k+1)-critical.
KW - Color critical graph
KW - k-degenerate graph
UR - http://www.scopus.com/inward/record.url?scp=84870170493&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84870170493&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2012.11.010
DO - 10.1016/j.disc.2012.11.010
M3 - Article
AN - SCOPUS:84870170493
SN - 0012-365X
VL - 313
SP - 366
EP - 374
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 4
ER -