Circular Chromatic Number of Signed Planar Graphs Without Cycles of Length 4 to 9

Chunyan Wei ()
Additional contact information
Chunyan Wei: Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, China

Mathematics, 2025, vol. 13, issue 3, 1-9

Abstract: Given a signed graph ( G , σ ) and a positive real number r , if there exists a vertex mapping c : V ( G ) → [ 0 , r ) satisfying that for every positive edge w x , 1 ≤ | c ( w ) − c ( x ) | ≤ r − 1 and for every negative edge w x , | c ( w ) − c ( x ) | ≤ r 2 − 1 or | c ( w ) − c ( x ) | ≥ r 2 + 1 , then ( G , σ ) admits a circular r -coloring. We use χ c ( G , σ ) to represent the circular chromatic number of ( G , σ ) , which is the minimum r , such that a circular r -coloring of ( G , σ ) exists. This paper proves that χ c ( G , σ ) < 4 , where ( G , σ ) is a simple signed planar graph containing no cycles of length 4 to 9. Moreover, we establish an upper bound for the chromatic number of such a graph to be 4 − 2 ⌊ v ( G ) + 1 2 ⌋ .

Keywords: signed planar graphs; circular colorings; strongly connected orientations (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/3/332/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/3/332/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:3:p:332-:d:1572519

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().