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 -