Bulletin, Institute of Mathematics, Academia Sinica
logo-Bulletin, Institute of Mathematics, Academia Sinica

Bulletin, Institute of Mathematics, Academia Sinica
logo_m-Bulletin, Institute of Mathematics, Academia Sinica

    Jump To中央區塊/Main Content :::
  • Editorial Board
  • Archives
  • Special Issues
  • Submission
  • Subscription
  • Contact Us
search
Bulletin of the Institute of
Mathematics Academia Sinica
NEW SERIES
  • Home
  • Archives
  • Bulletin of the Institute of Mathematics Academia Sinica (New Series)
  • Facebook
  • line
  • email
  • Twitter
  • Print
2025 / June Volume 20 No.2
Peaceful Colourings
Published Date
2025 / June
Title
Peaceful Colourings
Author
Chun-Hung Liu, Bruce Reed
Keyword
graph colouring, probabilistic method
Download
Download PDF
Pagination
95-129
Abstract

We introduce peaceful colourings, a variant of $h$-conflict free colourings. We call a colouring with no monochromatic edges $p$-peaceful if for each vertex $v$, there are at most $p$ neighbours of $v$ coloured with a colour appearing on another neighbour of $v$. An $h$-conflict-free colouring of a graph is a (vertex)-colouring with no monochromatic edges so that for every vertex $v$, the number of neighbours of $v$ which are coloured with a colour appearing on no other neighbour of $v$ is at least the minimum of $h$ and the degree of $v$. If $G$ is $\Delta$-regular then it has an $h$-conflict free colouring precisely if it has a $(\Delta-h)$-peaceful colouring. We focus on the minimum $p_\Delta$ of those $p$ for which every graph of maximum degree $\Delta$ has a $p$-peaceful colouring with $\Delta+1$ colours. We show that $p_\Delta > (1-\frac{1}{e}-o(1))\Delta$ and that for graphs of bounded codegree, $p_\Delta \leq (1-\frac{1}{e}+o(1))\Delta$. We ask if the latter result can be improved by dropping the bound on the codegree. As a partial result, we show that $p_\Delta \leq \frac{8000}{8001}\Delta$ for sufficiently large $\Delta$.

DOI
10.21915/BIMAS.2025201
https://doi.org/10.21915/BIMAS.2025201
AMS Subject
Classification
05C15
Received
2024-12-12
  • Editorial Board
  • Archives
  • Special Issues
  • Submission
  • Subscription
  • Contact Us

Institute of Mathematics, Academia Sinica 6th Floor, Astronomy‐Mathematics Building, No. 1, Section 4, Roosevelt Road, Taipei, 10617 Taiwan R.O.C.

Tel: +886‐2‐2368‐5999 ext. 382 Fax: +886‐2‐2368‐9771 Email: bulletin@math.sinica.edu.tw

© Copyright 2023. Math Sinica All Rights Reserved.Privacy Policy & Security Policy