Density of 3‐critical signed graphs

We say that a signed graph is k $k$‐critical if it is not k $k$‐colorable but every one of its proper subgraphs is k $k$‐colorable. Using the definition of colorability due to Naserasr, Wang, and Zhu that extends the notion of circular colorability, we prove that every 3‐critical signed graph on n $...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2024-09, Vol.107 (1), p.212-239
Main Authors: Beaudou, Laurent, Haxell, Penny, Nurse, Kathryn, Sen, Sagnik, Wang, Zhouningxin
Format: Article
Language:English
Subjects:
Apexes
circular coloring
critical signed graphs
edge‐density
Graph theory
homomorphism
Homomorphisms
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We say that a signed graph is k $k$‐critical if it is not k $k$‐colorable but every one of its proper subgraphs is k $k$‐colorable. Using the definition of colorability due to Naserasr, Wang, and Zhu that extends the notion of circular colorability, we prove that every 3‐critical signed graph on n $n$ vertices has at least 3n−12 $\frac{3n-1}{2}$ edges, and that this bound is asymptotically tight. It follows that every signed planar or projective‐planar graph of girth at least 6 is (circular) 3‐colorable, and for the projective‐planar case, this girth condition is best possible. To prove our main result, we reformulate it in terms of the existence of a homomorphism to the signed graph C3* ${C}_{3}^{* }$, which is the positive triangle augmented with a negative loop on each vertex.
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.23117