pith. sign in

arxiv: 1411.6668 · v1 · pith:6U22DUYWnew · submitted 2014-11-24 · 🧮 math.CO

Density of 5/2-critical graphs

classification 🧮 math.CO
keywords criticaleverygraphgraphsleastachievingboundcircular
0
0 comments X
read the original abstract

A graph G is 5/2-critical if G has no circular 5/2-coloring (or equivalently, homomorphism to C_5), but every proper subgraph of G has one. We prove that every 5/2-critical graph on n>=4 vertices has at least (5n-2)/4 edges, and list all 5/2-critical graphs achieving this bound. This implies that every planar or projective-planar graph of girth at least 10 is 5/2-colorable.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.