oalib
Search Results: 1 - 10 of 100 matches for " "
All listed articles are free for downloading (OA Articles)
Page 1 /100
Display every page Item
Nonrepetitive Colouring via Entropy Compression  [PDF]
Vida Dujmovi?,Gwena?l Joret,Jakub Kozik,David R. Wood
Computer Science , 2011,
Abstract: A vertex colouring of a graph is \emph{nonrepetitive} if there is no path whose first half receives the same sequence of colours as the second half. A graph is nonrepetitively $k$-choosable if given lists of at least $k$ colours at each vertex, there is a nonrepetitive colouring such that each vertex is coloured from its own list. It is known that every graph with maximum degree $\Delta$ is $c\Delta^2$-choosable, for some constant $c$. We prove this result with $c=1$ (ignoring lower order terms). We then prove that every subdivision of a graph with sufficiently many division vertices per edge is nonrepetitively 5-choosable. The proofs of both these results are based on the Moser-Tardos entropy-compression method, and a recent extension by Grytczuk, Kozik and Micek for the nonrepetitive choosability of paths. Finally, we prove that every graph with pathwidth $k$ is nonrepetitively $O(k^{2})$-colourable.
Nonrepetitive Colourings of Planar Graphs with $O(\log n)$ Colours  [PDF]
Vida Dujmovi?,Fabrizio Frati,Gwena?l Joret,David R. Wood
Computer Science , 2012,
Abstract: A vertex colouring of a graph is \emph{nonrepetitive} if there is no path for which the first half of the path is assigned the same sequence of colours as the second half. The \emph{nonrepetitive chromatic number} of a graph $G$ is the minimum integer $k$ such that $G$ has a nonrepetitive $k$-colouring. Whether planar graphs have bounded nonrepetitive chromatic number is one of the most important open problems in the field. Despite this, the best known upper bound is $O(\sqrt{n})$ for $n$-vertex planar graphs. We prove a $O(\log n)$ upper bound.
Graph colouring algorithms  [PDF]
Thore Husfeldt
Computer Science , 2015,
Abstract: This chapter presents an introduction to graph colouring algorithms. The focus is on vertex-colouring algorithms that work for general classes of graphs with worst-case performance guarantees in a sequential model of computation. The presentation aims to demonstrate the breadth of available techniques and is organized by algorithmic paradigm.
Colouring an Orthogonality Graph  [PDF]
C. D. Godsil,M. W. Newman
Mathematics , 2005,
Abstract: We deal with a graph colouring problem that arises in quantum information theory. Alice and Bob are each given a $\pm1$-vector of length $k$, and are to respond with $k$ bits. Their responses must be equal if they are given equal inputs, and distinct if they are given orthogonal inputs; however, they are not allowed to communicate any information about their inputs. They can always succeed using quantum entanglement, but their ability to succeed using only classical physics is equivalent to a graph colouring problem. We resolve the graph colouring problem, thus determining that they can succeed without entanglement exactly when $k\leq3$.
Greedy Graph Colouring is a Misleading Heuristic  [PDF]
Ciaran McCreesh,Patrick Prosser
Computer Science , 2013,
Abstract: State of the art maximum clique algorithms use a greedy graph colouring as a bound. We show that greedy graph colouring can be misleading, which has implications for parallel branch and bound.
Exact bounds for distributed graph colouring  [PDF]
Joel Rybicki,Jukka Suomela
Computer Science , 2015,
Abstract: We prove exact bounds on the time complexity of distributed graph colouring. If we are given a directed path that is properly coloured with $n$ colours, by prior work it is known that we can find a proper 3-colouring in $\frac{1}{2} \log^*(n) \pm O(1)$ communication rounds. We close the gap between upper and lower bounds: we show that for infinitely many $n$ the time complexity is precisely $\frac{1}{2} \log^* n$ communication rounds.
Fast, Responsive Decentralised Graph Colouring  [PDF]
Alessandro Checco,Douglas J. Leith
Computer Science , 2014,
Abstract: We solve, in a fully decentralised way (\ie with no message passing), the classic problem of colouring a graph. We propose a novel algorithm that is automatically responsive to topology changes, and we prove that it converges quickly to a proper colouring in $O(N\log{N})$ time with high probability for generic graphs (and in $O(\log{N})$ time if $\Delta=o(N)$) when the number of available colours is greater than $\Delta$, the maximum degree of the graph. We believe the proof techniques used in this work are of independent interest and provide new insight into the properties required to ensure fast convergence of decentralised algorithms.
Increasing the Efficiency of Graph Colouring Algorithms with a Representation Based on Vector Operations  [cached]
István Juhos,Jano I. van Hemert
Journal of Software , 2006, DOI: 10.4304/jsw.1.2.24-33
Abstract: We introduce a novel representation for the graph colouring problem, called the Integer Merge Model, which aims to reduce the time complexity of graph colouring algorithms. Moreover, this model provides useful information to aid in the creation of heuristics that can make the colouring process even faster. It also serves as a compact definition for the description of graph colouring algorithms. To verify the potential of the model, we use it in the complete algorithm DSATUR, and in two version of an incomplete approximation algorithm; an evolutionary algorithm and the same evolutionary algorithm extended with guiding heuristics. Both theoretical and empirical results are provided investigation is performed to show an increase in the efficiency of solving graph colouring problems. Two problem suites were used for the empirical evidence: a set of practical problem instances and a set of hard problem instances from the phase transition.
Graph colouring and the total Betti number  [PDF]
Alexander Engstrom
Mathematics , 2014,
Abstract: The total Betti number of the independence complex of a graph is an intriguing graph invariant. Kalai and Meshulam have raised the question on its relation to cycles and the chromatic number of a graph, and a recent conjecture on that theme was proved by Bonamy, Charbit and Thomasse. We show an upper bound on the total Betti number in terms of the number of vertex disjoint cycles in a graph. The main technique is discrete Morse theory and building poset maps. Ramanujan graphs with arbitrary chromatic number and girth log(n) is a classical construction. We show that any subgraph of them with less than n^0.003 vertices have smaller total Betti number than some planar graph of the same order, although it is part of a graph with high chromatic number.
A Note on Acyclic Edge Colouring of Star Graph Families  [PDF]
P. Shanasbabu, A. V. Chithra
American Journal of Computational Mathematics (AJCM) , 2015, DOI: 10.4236/ajcm.2015.53022
Abstract: A proper edge colouring f of a graph G is called acyclic if there are no bichromatic cycles in the graph. The acyclic edge chromatic number or acyclic chromatic index, denoted by \"\", is the minimum number of colours in an acyclic edge colouring of G. In this paper, we discuss the acyclic edge colouring of middle, central, total and line graphs of prime related star graph families. Also exact values of acyclic chromatic indices of such graphs are derived and some of their structural properties are discussed.
Page 1 /100
Display every page Item


Home
Copyright © 2008-2017 Open Access Library. All rights reserved.