E-viri
Recenzirano
-
Brewster, Richard C.; Moore, Benjamin
Journal of graph theory, February 2023, Letnik: 102, Številka: 2Journal Article
Given a graph G $G$, the k $k$‐mixing problem asks: Starting with a k $k$‐colouring of G $G$, can one obtain all k $k$‐colourings of G $G$ by changing the colour of only one vertex at a time, while at each step maintaining a k $k$‐colouring? More generally, for a graph H $H$, the H $H$‐mixing problem asks: Can one obtain all homomorphisms G → H $G\to H$, starting from one homomorphism f $f$, by changing the image of only one vertex at a time, while at each step maintaining a homomorphism G → H $G\to H$? This paper focuses on a generalization of k $k$‐colourings, namely, (p , q ) $(p,q)$‐circular colourings. We show that when 2 < p q < 4 $2\lt \frac{p}{q}\lt 4$, a graph G $G$ is (p , q ) $(p,q)$‐mixing if and only if for any (p , q ) $(p,q)$‐colouring f $f$ of G $G$, and any cycle C $C$ of G $G$, the wind of the cycle under the colouring equals a particular value (which intuitively corresponds to having no wind). As a consequence we show that (p , q ) $(p,q)$‐mixing is closed under a restricted homomorphism called a fold. Using this, we deduce that (2 k + 1 , k ) $(2k+1,k)$‐mixing is co‐NP‐complete for all k ∈ N $k\in {\mathbb{N}}$, and by similar ideas we show that if the circular chromatic number of a connected graph G $G$ is 2 k + 1 k $\frac{2k+1}{k}$, then G $G$ folds to C2 k + 1 ${C}_{2k+1}$. We use the characterization to settle a conjecture of Brewster and Noel, specifically that the circular mixing number of bipartite graphs is 2. Lastly, we give a polynomial time algorithm for (p , q ) $(p,q)$‐mixing in planar graphs when 3 ≤ p q < 4 $3\le \frac{p}{q}\lt 4$.
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|
Vir: Osebne bibliografije
in: SICRIS
To gradivo vam je dostopno v celotnem besedilu. Če kljub temu želite naročiti gradivo, kliknite gumb Nadaljuj.