Relevant bibliographies by topics / Odd colouring / Journal articles
To see the other types of publications on this topic, follow the link: Odd colouring.

Journal articles on the topic 'Odd colouring'

Author: Grafiati
Published: 25 May 2024
Last updated: 31 July 2025

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 39 journal articles for your research on the topic 'Odd colouring.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

KANG, ROSS J., and FRANÇOIS PIROT. "Distance Colouring Without One Cycle Length." Combinatorics, Probability and Computing 27, no. 5 (2018): 794–807. http://dx.doi.org/10.1017/s0963548318000068.

Full text
Abstract:
We consider distance colourings in graphs of maximum degree at most d and how excluding one fixed cycle of length ℓ affects the number of colours required as d → ∞. For vertex-colouring and t ⩾ 1, if any two distinct vertices connected by a path of at most t edges are required to be coloured differently, then a reduction by a logarithmic (in d) factor against the trivial bound O(dt) can be obtained by excluding an odd cycle length ℓ ⩾ 3t if t is odd or by excluding an even cycle length ℓ ⩾ 2t + 2. For edge-colouring and t ⩾ 2, if any two distinct edges connected by a path of fewer than t edges
APA, Harvard, Vancouver, ISO, and other styles
2

ZELENYUK, YEVHEN, and YULIYA ZELENYUK. "COUNTING SYMMETRIC BRACELETS." Bulletin of the Australian Mathematical Society 89, no. 3 (2013): 431–36. http://dx.doi.org/10.1017/s0004972713000701.

Full text
Abstract:
AbstractAn $r$-ary necklace (bracelet) of length $n$ is an equivalence class of $r$-colourings of vertices of a regular $n$-gon, taking all rotations (rotations and reflections) as equivalent. A necklace (bracelet) is symmetric if a corresponding colouring is invariant under some reflection. We show that the number of symmetric $r$-ary necklaces (bracelets) of length $n$ is $\frac{1}{2} (r+ 1){r}^{n/ 2} $ if $n$ is even, and ${r}^{(n+ 1)/ 2} $ if $n$ is odd.
APA, Harvard, Vancouver, ISO, and other styles
3

Kang, Dong Yeap, and Sang-Il Oum. "Improper colouring of graphs with no odd clique minor." Combinatorics, Probability and Computing 28, no. 5 (2019): 740–54. http://dx.doi.org/10.1017/s0963548318000548.

Full text
Abstract:
AbstractAs a strengthening of Hadwiger’s conjecture, Gerards and Seymour conjectured that every graph with no oddKtminor is (t− 1)-colourable. We prove two weaker variants of this conjecture. Firstly, we show that for eacht⩾ 2, every graph with no oddKtminor has a partition of its vertex set into 6t− 9 setsV1, …,V6t−9such that eachViinduces a subgraph of bounded maximum degree. Secondly, we prove that for eacht⩾ 2, every graph with no odd Kt minor has a partition of its vertex set into 10t−13 setsV1,…,V10t−13such that eachViinduces a subgraph with components of bounded size. The second theorem
APA, Harvard, Vancouver, ISO, and other styles
4

KAWARABAYASHI, KEN-ICHI. "A Weakening of the Odd Hadwiger's Conjecture." Combinatorics, Probability and Computing 17, no. 6 (2008): 815–21. http://dx.doi.org/10.1017/s0963548308009462.

Full text
Abstract:
Gerards and Seymour (see [10], p. 115) conjectured that if a graph has no odd complete minor of order l, then it is (l − 1)-colourable. This is an analogue of the well-known conjecture of Hadwiger, and in fact, this would immediately imply Hadwiger's conjecture. The current best-known bound for the chromatic number of graphs with no odd complete minor of order l is $O(l \sqrt{\log l})$ by the recent result by Geelen, Gerards, Reed, Seymour and Vetta [8], and by Kawarabayashi [12] later, independently. But it seems very hard to improve this bound since this would also improve the current best-k
APA, Harvard, Vancouver, ISO, and other styles
5

BOUSQUET, NICOLAS, LOUIS ESPERET, ARARAT HARUTYUNYAN, and RÉMI DE JOANNIS DE VERCLOS. "Exact Distance Colouring in Trees." Combinatorics, Probability and Computing 28, no. 2 (2018): 177–86. http://dx.doi.org/10.1017/s0963548318000378.

Full text
Abstract:
For an integer q ⩾ 2 and an even integer d, consider the graph obtained from a large complete q-ary tree by connecting with an edge any two vertices at distance exactly d in the tree. This graph has clique number q + 1, and the purpose of this short note is to prove that its chromatic number is Θ((d log q)/log d). It was not known that the chromatic number of this graph grows with d. As a simple corollary of our result, we give a negative answer to a problem of van den Heuvel and Naserasr, asking whether there is a constant C such that for any odd integer d, any planar graph can be coloured wi
APA, Harvard, Vancouver, ISO, and other styles
6

Bryant, Darryn, and C. A. Rodger. "On the completion of latin rectangles to symmetric latin squares." Journal of the Australian Mathematical Society 76, no. 1 (2004): 109–24. http://dx.doi.org/10.1017/s1446788700008739.

Full text
Abstract:
AbstractWe find necessary and sufficient conditions for completing an arbitrary 2 by n latin rectangle to an n by n symmetric latin square, for completing an arbitrary 2 by n latin rectangle to an n by n unipotent symmetric latin square, and for completing an arbitrary 1 by n latin rectangle to an n by n idempotent symmetric latin square. Equivalently, we prove necessary and sufficient conditions for the existence of an (n−1)-edge colouring of Kn (n even), and for n-edge colouring of Kn (n odd) in which the colours assigned to the edges incident with two vertices are specified in advance.
APA, Harvard, Vancouver, ISO, and other styles
7

D. Kavitha Thenmozhi. "Optimizing Balanced Networks with Strong Equitable Edge Colouring." Journal of Information Systems Engineering and Management 10, no. 8s (2025): 545–50. https://doi.org/10.52783/jisem.v10i8s.1110.

Full text
Abstract:
Equitable edge colouring is a sophisticated network labelling technique with no more than one difference in the number of edges between any two colour groups. In this study, we applied the equitable edge-coloring technique to triangulated networks, utilizing the minimal number of edge colours, denoted by Δ. The structural characteristics of horse stride, branch flow, and tri-wing networks are presented in this research. The technique ensures optimized network performance, regardless of whether the triangular graphs involved are in even or odd quantities, reinforcing the robustness of this meth
APA, Harvard, Vancouver, ISO, and other styles
8

KINNERSLEY, WILLIAM B., KEVIN G. MILANS, and DOUGLAS B. WEST. "Degree Ramsey Numbers of Graphs." Combinatorics, Probability and Computing 21, no. 1-2 (2012): 229–53. http://dx.doi.org/10.1017/s0963548311000617.

Full text
Abstract:
Let HG mean that every s-colouring of E(H) produces a monochromatic copy of G in some colour class. Let the s-colour degree Ramsey number of a graph G, written RΔ(G; s), be min{Δ(H): HG}. If T is a tree in which one vertex has degree at most k and all others have degree at most ⌈k/2⌉, then RΔ(T; s) = s(k − 1) + ϵ, where ϵ = 1 when k is odd and ϵ = 0 when k is even. For general trees, RΔ(T; s) ≤ 2s(Δ(T) − 1).To study sharpness of the upper bound, consider the double-starSa,b, the tree whose two non-leaf vertices have degrees a and b. If a ≤ b, then RΔ(Sa,b; 2) is 2b − 2 when a < b and b is e
APA, Harvard, Vancouver, ISO, and other styles
9

Stone, Phil. "Non-Mathematical Musings on Information Theory and Networked Musical Practice." Organised Sound 26, no. 3 (2021): 327–32. http://dx.doi.org/10.1017/s1355771821000418.

Full text
Abstract:
Claude Shannon’s 1948 paper ‘A Mathematical Theory of Communication’ provided the essential foundation for the digital/information revolution that enables these very pixels to glow in meaningful patterns and permeates nearly every aspect of modern life. Information Theory, born fully grown from this paper, has been applied and mis-applied to a multitude of disciplines in the last 70-odd years, from quantum physics to psychology. Shannon himself famously decried those jumping on the ‘scientific bandwagon’ of Information Theory without sufficient mathematical rigour. Nevertheless, having a brief
APA, Harvard, Vancouver, ISO, and other styles
10

Jayawardene, C. J., J. N. Senadheera, K. A. S. N. Fernando, and W. C. W. Navaratna. "On Star-critical (K1,n, K1,m + e) Ramsey Numbers." Annals of Pure and Applied Mathematics 22, no. 02 (2020): 75–82. http://dx.doi.org/10.22457/apam.v22n2a02702.

Full text
Abstract:
We say that Kn → (G,H), if for every red/blue colouring of edges of the complete graph Kn, there exists a red copy of G, or a blue copy of H in the colouring of Kn. The Ramsey number r(G,H) is the smallest positive integer n such that Kn → (G,H). Let r(n,m)=r(Kn, Km). A closely related concept of Ramsey numbers is the Star-critical Ramsey number r*(G, H) defined as the largest value of k such that K r(G,H)-1 ˅ K 1,k → (G,H). Literature on survey papers in this area reveals many unsolved problems related to these numbers. One of these problems is the calculation of Ramsey numbers for certain cl
APA, Harvard, Vancouver, ISO, and other styles
11

Chistikov, Dmitry, Olga Goulko, Adrian Kent, and Mike Paterson. "Globe-hopping." Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 476, no. 2238 (2020): 20200038. http://dx.doi.org/10.1098/rspa.2020.0038.

Full text
Abstract:
We consider versions of the grasshopper problem (Goulko & Kent 2017 Proc. R. Soc. A 473 , 20170494) on the circle and the sphere, which are relevant to Bell inequalities. For a circle of circumference 2 π , we show that for unconstrained lawns of any length and arbitrary jump lengths, the supremum of the probability for the grasshopper’s jump to stay on the lawn is one. For antipodal lawns, which by definition contain precisely one of each pair of opposite points and have length π , we show this is true except when the jump length ϕ is of the form π ( p / q ) with p , q coprime and p odd.
APA, Harvard, Vancouver, ISO, and other styles
12

Javadi, R., F. Khoeini, G. R. Omidi, and A. Pokrovskiy. "On the Size-Ramsey Number of Cycles." Combinatorics, Probability and Computing 28, no. 06 (2019): 871–80. http://dx.doi.org/10.1017/s0963548319000221.

Full text
Abstract:
AbstractFor given graphs G1,…, Gk, the size-Ramsey number $\hat R({G_1}, \ldots ,{G_k})$ is the smallest integer m for which there exists a graph H on m edges such that in every k-edge colouring of H with colours 1,…,k, H contains a monochromatic copy of Gi of colour i for some 1 ≤ i ≤ k. We denote $\hat R({G_1}, \ldots ,{G_k})$ by ${\hat R_k}(G)$ when G1 = ⋯ = Gk = G.Haxell, Kohayakawa and Łuczak showed that the size-Ramsey number of a cycle Cn is linear in n, ${\hat R_k}({C_n}) \le {c_k}n$ for some constant ck. Their proof, however, is based on Szemerédi’s regularity lemma so no specific con
APA, Harvard, Vancouver, ISO, and other styles
13

Das, Shagnik, and Andrew Treglown. "Ramsey properties of randomly perturbed graphs: cliques and cycles." Combinatorics, Probability and Computing 29, no. 6 (2020): 830–67. http://dx.doi.org/10.1017/s0963548320000231.

Full text
Abstract:
AbstractGiven graphs H1, H2, a graph G is (H1, H2) -Ramsey if, for every colouring of the edges of G with red and blue, there is a red copy of H1 or a blue copy of H2. In this paper we investigate Ramsey questions in the setting of randomly perturbed graphs. This is a random graph model introduced by Bohman, Frieze and Martin [8] in which one starts with a dense graph and then adds a given number of random edges to it. The study of Ramsey properties of randomly perturbed graphs was initiated by Krivelevich, Sudakov and Tetali [30] in 2006; they determined how many random edges must be added to
APA, Harvard, Vancouver, ISO, and other styles
14

Matos Camacho, Stephan, and Ingo Schiermeyer. "Colourings of graphs with two consecutive odd cycle lengths." Discrete Mathematics 309, no. 15 (2009): 4916–19. http://dx.doi.org/10.1016/j.disc.2008.04.042.

Full text
APA, Harvard, Vancouver, ISO, and other styles
15

Šparl, P., and J. Žerovnik. "A note onn-tuple colourings and circular colourings of planar graphs with large odd girth." International Journal of Computer Mathematics 84, no. 12 (2007): 1743–46. http://dx.doi.org/10.1080/00207160701327721.

Full text
APA, Harvard, Vancouver, ISO, and other styles
16

Sigamani, Santhosh, Sharmila Banu Vm, Hemalatha V, Venkatakrishnan V, and Dhandapani R. "OPTIMIZATION STUDY ON EXTRACTION & PURIFICATION OF PHYCOERYTHRIN FROM RED ALGAE KAPPAPHYCUS ALVAREZII." Asian Journal of Pharmaceutical and Clinical Research 10, no. 2 (2017): 297. http://dx.doi.org/10.22159/ajpcr.2017.v10i2.15598.

Full text
Abstract:
Objective: The current study focuses on R-Phycoerythrin pigment production from Seaweed using different chemical and physical conditions. Methods: In the present study Seaweed was collected from Rameshwaram and identified by CS-MCRI Institute, Mandapam. The collected seaweed was then washed using distilled water for further processing. Using a sterile knife the seaweed was cut into small pieces. The chopped seaweeds were then weighed and subjected to different optimization procedures for pigment production. These equally weighed seaweeds were treated with three varying Buffers at different pH,
APA, Harvard, Vancouver, ISO, and other styles
17

Nyoni-Kachambwa, Princess, Wanapa Naravage, Nigel F James, and Marc Van der Putten. "A preliminary study of skin bleaching and factors associated with skin bleaching among women living in Zimbabwe." African Health Sciences 21, no. 1 (2021): 132–9. http://dx.doi.org/10.4314/ahs.v21i1.18.

Full text
Abstract:
Background: Skin bleaching was reported to be commonly practiced among women and Africa was reported to be one of the most affected yet the subject is not given much attention in public health research in Zimbabwe despite the adverse effects of skin bleaching on health.
 Method: This study was an exploratory cross-sectional survey to explore skin bleaching, skin bleaching patterns and factors associated with skin bleaching among women living in Zimbabwe. An online self-administered questionnaire was sent out to women on social network i.e. WhatsApp, Facebook, LinkedIn and Twitter.
 F
APA, Harvard, Vancouver, ISO, and other styles
18

Dai, Tianjiao, Qiancheng Ouyang, and François Pirot. "New Bounds for Odd Colourings of Graphs." Electronic Journal of Combinatorics 31, no. 4 (2024). http://dx.doi.org/10.37236/12110.

Full text
Abstract:
Given a graph $G$, a vertex-colouring $\sigma$ of $G$, and a subset $X\subseteq V(G)$, a colour $x \in \sigma(X)$ is said to be odd for $X$ in $\sigma$ if it has an odd number of occurrences in $X$. We say that $\sigma$ is an odd colouring of $G$ if it is proper and every (open) neighbourhood has an odd colour in $\sigma$. The odd chromatic number of a graph $G$, denoted by $\chi_o(G)$, is the minimum $k\in\mathbb{N}$ such that an odd colouring $\sigma \colon V(G)\to [k]$ exists. In a recent paper, Caro, Petruševski and Škrekovski conjectured that every connected graph of maximum degree $\Delt
APA, Harvard, Vancouver, ISO, and other styles
19

Petr, Jan, and Julien Portier. "The Odd Chromatic Number of a Planar Graph is at Most 8." Graphs and Combinatorics 39, no. 2 (2023). http://dx.doi.org/10.1007/s00373-023-02617-z.

Full text
Abstract:
AbstractPetruševski and Škrekovski recently introduced the notion of an odd colouring of a graph: a proper vertex colouring of a graph G is said to be odd if for each non-isolated vertex $$x \in V(G)$$ x ∈ V ( G ) there exists a colour c appearing an odd number of times in its neighbourhood N(x). Petruševski and Škrekovski proved that for any planar graph G there is an odd colouring using at most 9 colours and, together with Caro, showed that 8 colours are enough for a significant family of planar graphs. We show that 8 colours suffice for all planar graphs.
APA, Harvard, Vancouver, ISO, and other styles
20

Belmonte, Rémy, Ararat Harutyunyan, Noleen Köhler, and Nikolaos Melissinos. "Odd chromatic number of graph classes." Journal of Graph Theory, November 6, 2024. http://dx.doi.org/10.1002/jgt.23200.

Full text
Abstract:
AbstractA graph is called odd (respectively, even) if every vertex has odd (respectively, even) degree. Gallai proved that every graph can be partitioned into two even induced subgraphs, or into an odd and an even induced subgraph. We refer to a partition into odd subgraphs as an odd colouring of . Scott proved that a connected graph admits an odd colouring if and only if it has an even number of vertices. We say that a graph is ‐odd colourable if it can be partitioned into at most odd induced subgraphs. The odd chromatic number of , denoted by , is the minimum integer for which is ‐odd colour
APA, Harvard, Vancouver, ISO, and other styles
21

Kamčev, Nina, and Christoph Spiegel. "Another Note on Intervals in the Hales–Jewett Theorem." Electronic Journal of Combinatorics 29, no. 1 (2022). http://dx.doi.org/10.37236/9400.

Full text
Abstract:
The Hales–Jewett Theorem states that any $r$–colouring of $[m]^n$ contains a monochromatic combinatorial line if $n$ is large enough. Shelah's proof of the theorem implies that for $m = 3$ there always exists a monochromatic combinatorial line whose set of active coordinates is the union of at most $r$ intervals. For odd $r$, Conlon and Kamčev constructed $r$–colourings for which it cannot be fewer than $r$ intervals. However, we show that for even $r$ and large $n$, any $r$–colouring of $[3]^n$ contains a monochromatic combinatorial line whose set of active coordinates is the union of at most
APA, Harvard, Vancouver, ISO, and other styles
22

Davies, James. "Odd Distances in Colourings of the Plane." Geometric and Functional Analysis, January 30, 2024. http://dx.doi.org/10.1007/s00039-024-00659-w.

Full text
APA, Harvard, Vancouver, ISO, and other styles
23

Rojas Anríquez, Alberto, and Maya Stein. "3-Colouring $$P_t$$-Free Graphs Without Short Odd Cycles." Algorithmica, October 17, 2022. http://dx.doi.org/10.1007/s00453-022-01049-0.

Full text
APA, Harvard, Vancouver, ISO, and other styles
24

Burgess, Andrea, and Francesca Merola. "On equitably 2‐colourable odd cycle decompositions." Journal of Combinatorial Designs, April 18, 2024. http://dx.doi.org/10.1002/jcd.21937.

Full text
Abstract:
AbstractAn ‐cycle decomposition of is said to be equitably 2‐colourable if there is a 2‐vertex‐colouring of such that each colour is represented (approximately) an equal number of times on each cycle: more precisely, we ask that in each cycle of the decomposition, each colour appears on or of the vertices of . In this paper we study the existence of equitably 2‐colourable ‐cycle decompositions of , where is odd, and prove the existence of such a decomposition for (mod ).
APA, Harvard, Vancouver, ISO, and other styles
25

Knox, Fiachra, and Robert Šámal. "Linear Bound for Majority Colourings of Digraphs." Electronic Journal of Combinatorics 25, no. 3 (2018). http://dx.doi.org/10.37236/6762.

Full text
Abstract:
Given $\eta \in [0, 1]$, a colouring $C$ of $V(G)$ is an $\eta$-majority colouring if at most $\eta d^+(v)$ out-neighbours of $v$ have colour $C(v)$, for any $v \in V(G)$. We show that every digraph $G$ equipped with an assignment of lists $L$, each of size at least $k$, has a $2/k$-majority $L$-colouring. For even $k$ this is best possible, while for odd $k$ the constant $2/k$ cannot be replaced by any number less than $2/(k+1)$. This generalizes a result of Anholcer, Bosek and Grytczuk, who proved the cases $k=3$ and $k=4$ and claim a weaker result for general $k$.
APA, Harvard, Vancouver, ISO, and other styles
26

Kriesell, Matthias, and Anders Pedersen. "On graphs double-critical with respect to the colouring number." Discrete Mathematics & Theoretical Computer Science Vol. 17 no.2, Graph Theory (2015). http://dx.doi.org/10.46298/dmtcs.2129.

Full text
Abstract:
International audience The colouring number col($G$) of a graph $G$ is the smallest integer $k$ for which there is an ordering of the vertices of $G$ such that when removing the vertices of $G$ in the specified order no vertex of degree more than $k-1$ in the remaining graph is removed at any step. An edge $e$ of a graph $G$ is said to be <i>double</i>-col-<i>critical</i> if the colouring number of $G-V(e)$ is at most the colouring number of $G$ minus 2. A connected graph G is said to be double-col-critical if each edge of $G$ is double-col-critical. We characterise the
APA, Harvard, Vancouver, ISO, and other styles
27

Steiner, Raphael. "Improved bound for improper colourings of graphs with no odd clique minor." Combinatorics, Probability and Computing, September 30, 2022, 1–8. http://dx.doi.org/10.1017/s0963548322000268.

Full text
Abstract:
Abstract Strengthening Hadwiger’s conjecture, Gerards and Seymour conjectured in 1995 that every graph with no odd $K_t$ -minor is properly $(t-1)$ -colourable. This is known as the Odd Hadwiger’s conjecture. We prove a relaxation of the above conjecture, namely we show that every graph with no odd $K_t$ -minor admits a vertex $(2t-2)$ -colouring such that all monochromatic components have size at most $\lceil \frac{1}{2}(t-2) \rceil$ . The bound on the number of colours is optimal up to a factor of $2$ , improves previous bounds for the same problem by Kawarabayashi (2008, Combin. Probab. Com
APA, Harvard, Vancouver, ISO, and other styles
28

Aboulker, Pierre, Guillaume Aubian, and Chien-Chung Huang. "Vizing's and Shannon's Theorems for Defective Edge Colouring." Electronic Journal of Combinatorics 29, no. 4 (2022). http://dx.doi.org/10.37236/11049.

Full text
Abstract:
We call a multigraph $(k,d)$-edge colourable if its edge set can be partitioned into $k$ subgraphs of maximum degree at most $d$ and denote as $\chi'_{d}(G)$ the minimum $k$ such that $G$ is $(k,d)$-edge colourable. We prove that for every odd integer $d$, every multigraph $G$ with maximum degree $\Delta$ is $(\lceil \frac{3\Delta - 1}{3d - 1} \rceil, d)$-edge colourable and this bound is attained for all values of $\Delta$ and $d$. An easy consequence of Vizing's Theorem is that, for every (simple) graph $G,$ $\chi'_{d}(G) \in \{ \lceil \frac{\Delta}{d} \rceil, \lceil \frac{\Delta+1}{d} \rcei
APA, Harvard, Vancouver, ISO, and other styles
29

Cameron, Kathie, and Jack Edmonds. "Finding a Strong Stable Set or a Meyniel Obstruction in any Graph." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AE,..., Proceedings (2005). http://dx.doi.org/10.46298/dmtcs.3411.

Full text
Abstract:
International audience A strong stable set in a graph $G$ is a stable set that contains a vertex of every maximal clique of $G$. A Meyniel obstruction is an odd circuit with at least five vertices and at most one chord. Given a graph $G$ and a vertex $v$ of $G$, we give a polytime algorithm to find either a strong stable set containing $v$ or a Meyniel obstruction in $G$. This can then be used to find in any graph, a clique and colouring of the same size or a Meyniel obstruction.
APA, Harvard, Vancouver, ISO, and other styles
30

Kang, Ross J., and Willem Van Loon. "Tree-Like Distance Colouring for Planar Graphs of Sufficient Girth." Electronic Journal of Combinatorics 26, no. 1 (2019). http://dx.doi.org/10.37236/8220.

Full text
Abstract:
Given a multigraph $G$ and a positive integer $t$, the distance-$t$ chromatic index of $G$ is the least number of colours needed for a colouring of the edges so that every pair of distinct edges connected by a path of fewer than $t$ edges must receive different colours. Let $\pi'_t(d)$ and $\tau'_t(d)$ be the largest values of this parameter over the class of planar multigraphs and of (simple) trees, respectively, of maximum degree $d$. We have that $\pi'_t(d)$ is at most and at least a non-trivial constant multiple larger than $\tau'_t(d)$. (We conjecture $\limsup_{d\to\infty}\pi'_2(d)/\tau'_
APA, Harvard, Vancouver, ISO, and other styles
31

Zatesko, Leandro, Renato Carmo, André L. P. Guedes, Raphael C. S. Machado, and Celina M. H. Figueiredo. "The hardness of recognising poorly matchable graphs and the hunting of the d-snark." RAIRO - Operations Research, March 18, 2024. http://dx.doi.org/10.1051/ro/2024068.

Full text
Abstract:
Abstract. An r-graph is an r-regular graph G on an even number of vertices where every odd set X ⊆V(G) is connected by at least r edges to its complement V(G) \ X. Every r-graph has a perfect matching and in a poorly matchable r-graph every pair of perfect matchings intersect, which implies that poorly matchable r-graphs are not r-edge-colourable. We prove, for each fixed r ≥ 3, that poorly matchable r-graph recognition is coNP-complete, an indication that, for each odd d ≥ 3, it may be a hard problem to recognise d-regular (d−1)-edge-connected non-d-edge-colourable graphs, referred to as d-sn
APA, Harvard, Vancouver, ISO, and other styles
32

Grable, David A., and Alessandro Panconesi. "Fast Distributed Algorithms for Brooks-Vizing Colourings (Extended Abstract)." BRICS Report Series 4, no. 37 (1997). http://dx.doi.org/10.7146/brics.v4i37.18963.

Full text
Abstract:
Vertex colouring is a much studied problem in combinatorics and computer science for its theoretical as well as its practical aspects. In this paper<br />we are concerned with the "distributed" version of a question stated by Vizing, concerning a Brooks-like theorem for sparse graphs. Roughly, the question asks whether there exist colourings using many fewer than<br />Delta colours, where Delta denotes the maximum degree of the graph, provided that some sparsity conditions are satisfied. In this paper we show that such colourings not only exist, but that they can be quickly compute
APA, Harvard, Vancouver, ISO, and other styles
33

DENG, MINGYANG, JONATHAN TIDOR, and YUFEI ZHAO. "Uniform sets with few progressions via colourings." Mathematical Proceedings of the Cambridge Philosophical Society, May 15, 2025, 1–25. https://doi.org/10.1017/s0305004125000106.

Full text
Abstract:
Abstract Ruzsa asked whether there exist Fourier-uniform subsets of $\mathbb Z/N\mathbb Z$ with density $\alpha$ and 4-term arithmetic progression (4-AP) density at most $\alpha^C$ , for arbitrarily large C. Gowers constructed Fourier uniform sets with density $\alpha$ and 4-AP density at most $\alpha^{4+c}$ for some small constant $c \gt 0$ . We show that an affirmative answer to Ruzsa’s question would follow from the existence of an $N^{o(1)}$ -colouring of [N] without symmetrically coloured 4-APs. For a broad and natural class of constructions of Fourier-uniform subsets of $\mathbb Z/N\math
APA, Harvard, Vancouver, ISO, and other styles
34

Atkins, Ross, Puck Rombach, and Fiona Skerman. "Guessing Numbers of Odd Cycles." Electronic Journal of Combinatorics 24, no. 1 (2017). http://dx.doi.org/10.37236/5964.

Full text
Abstract:
For a given number of colours, $s$, the guessing number of a graph is the base $s$ logarithm of the size of the largest family of colourings of the vertex set of the graph such that the colour of each vertex can be determined from the colours of the vertices in its neighbourhood. An upper bound for the guessing number of the $n$-vertex cycle graph $C_n$ is $n/2$. It is known that the guessing number equals $n/2$ whenever $n$ is even or $s$ is a perfect square. We show that, for any given integer $s \geq 2$, if $a$ is the largest factor of $s$ less than or equal to $\sqrt{s}$, for sufficiently
APA, Harvard, Vancouver, ISO, and other styles
35

Lambie-Hanson, C., and D. T. Soukup. "Extremal triangle-free and odd-cycle-free colourings of uncountable graphs." Acta Mathematica Hungarica, June 30, 2020. http://dx.doi.org/10.1007/s10474-020-01053-2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
36

Przybyło, Jakub. "On Decomposing Graphs of Large Minimum Degree into Locally Irregular Subgraphs." Electronic Journal of Combinatorics 23, no. 2 (2016). http://dx.doi.org/10.37236/5173.

Full text
Abstract:
A locally irregular graph is a graph whose adjacent vertices have distinct degrees. We say that a graph G can be decomposed into k locally irregular subgraphs if its edge set may be partitioned into k subsets each of which induces a locally irregular subgraph in G. It has been conjectured that apart from the family of exceptions which admit no such decompositions, i.e., odd paths, odd cycles and a special class of graphs of maximum degree 3, every connected graph can be decomposed into 3 locally irregular subgraphs. Using a combination of a probabilistic approach and some known theorems on deg
APA, Harvard, Vancouver, ISO, and other styles
37

Morgan, Kerri, and Graham Farr. "Certificates of Factorisation for a Class of Triangle-Free Graphs." Electronic Journal of Combinatorics 16, no. 1 (2009). http://dx.doi.org/10.37236/164.

Full text
Abstract:
The chromatic polynomial $P(G,\lambda)$ gives the number of $\lambda$-colourings of a graph. If $P(G,\lambda)=P(H_{1},\lambda)P(H_{2},\lambda)/P(K_{r},\lambda)$, then the graph $G$ is said to have a chromatic factorisation with chromatic factors $H_{1}$ and $H_{2}$. It is known that the chromatic polynomial of any clique-separable graph has a chromatic factorisation. In this paper we construct an infinite family of graphs that have chromatic factorisations, but have chromatic polynomials that are not the chromatic polynomial of any clique-separable graph. A certificate of factorisation, that i
APA, Harvard, Vancouver, ISO, and other styles
38

Taylor, Nick. "LEGO and the Infrastructural Limits of Open Play." M/C Journal 26, no. 3 (2023). http://dx.doi.org/10.5204/mcj.2945.

Full text
Abstract:
LEGO and Adult Hobbyism For much of its history, LEGO has been regarded as a – if not the – children’s toy. Partially through The LEGO Group (TLG)’s own careful deployment of research on constructivist learning, the building system’s recombinatory logic, bright colours, and foot-destroying durability have become associated with paradigmatic notions of what children’s play is and does (Giddings; Maddalena). And yet the world of adult LEGO hobbyism is complex, rich, and worthy of scholarly attention in its own regard. As recent headlines about the popularity of toys among adults have indicated,
APA, Harvard, Vancouver, ISO, and other styles
39

Brien, Donna Lee. "Demon Monsters or Misunderstood Casualties?" M/C Journal 24, no. 5 (2021). http://dx.doi.org/10.5204/mcj.2845.

Full text
Abstract:
Over the past century, many books for general readers have styled sharks as “monsters of the deep” (Steele). In recent decades, however, at least some writers have also turned to representing how sharks are seriously threatened by human activities. At a time when media coverage of shark sightings seems ever increasing in Australia, scholarship has begun to consider people’s attitudes to sharks and how these are formed, investigating the representation of sharks (Peschak; Ostrovski et al.) in films (Le Busque and Litchfield; Neff; Schwanebeck), newspaper reports (Muter et al.), and social media
APA, Harvard, Vancouver, ISO, and other styles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography