Log in

Relevant bibliographies by topics / Graph colouring / Journal articles

To see the other types of publications on this topic, follow the link: Graph colouring.

Journal articles on the topic 'Graph colouring'

Author: Grafiati

Published: 4 June 2021

Last updated: 8 June 2024

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

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Graph 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

LEHNER, FLORIAN. "Random Colourings and Automorphism Breaking in Locally Finite Graphs." Combinatorics, Probability and Computing 22, no. 6 (September 16, 2013): 885–909. http://dx.doi.org/10.1017/s0963548313000382.

Full text

Abstract:

A colouring of a graphGis called distinguishing if its stabilizer in AutGis trivial. It has been conjectured that, if every automorphism of a locally finite graph moves infinitely many vertices, then there is a distinguishing 2-colouring. We study properties of random 2-colourings of locally finite graphs and show that the stabilizer of such a colouring is almost surely nowhere dense in AutGand a null set with respect to the Haar measure on the automorphism group. We also investigate random 2-colourings in several classes of locally finite graphs where the existence of a distinguishing 2-colouring has already been established. It turns out that in all of these cases a random 2-colouring is almost surely distinguishing.

APA, Harvard, Vancouver, ISO, and other styles

2

Madaras, Tomáš, and Mária Šurimová. "Facial Homogeneous Colouring of Graphs." Symmetry 13, no. 7 (July 6, 2021): 1213. http://dx.doi.org/10.3390/sym13071213.

Full text

Abstract:

A proper colouring of a plane graph G is called facially homogeneous if it uses the same number of colours for every face of G. We study various sufficient conditions of facial homogeneous colourability of plane graphs, its relation to other facial colourings, and the extension of this concept for embedded graphs in general.

APA, Harvard, Vancouver, ISO, and other styles

3

Voloshin, V. "A note on the conditional chromatic polynomial." Glasgow Mathematical Journal 36, no. 3 (September 1994): 265–67. http://dx.doi.org/10.1017/s0017089500030834.

Full text

Abstract:

In this note we consider a finite graph without loops and multiple edges. The colouring of a graph G in λ colours is the colouring of its vertices in such a way that no two of adjacent vertices have the same colours and the number of used colours does not exceed λ [1, 4]. Two colourings of graph G are called different if there exists at least one vertex which changes colour when passing from one colouring to another.

APA, Harvard, Vancouver, ISO, and other styles

4

V, Kaviyaa, and Manikandan M. "Characterization of a Vertex Colouring of a Double Layered Complete Fuzzy Graph Using ? – CUT." International Journal for Research in Applied Science and Engineering Technology 10, no. 11 (November 30, 2022): 1367–73. http://dx.doi.org/10.22214/ijraset.2022.47510.

Full text

Abstract:

Abstract: In this paper we defined a new fuzzy graph named Double layered complete fuzzy graph. (DLCFG). The double layered complete fuzzy graph gives a 3-D structure. Further we introduced vertex colouring of the double layered complete fuzzy graph using α-cut. Keywords: Graph theory, Fuzzy graph, colouring of graphs, double layered fuzzy graph, complete fuzzy graph, alpha cut, colouring of double layered fuzzy graph, colouring of double layered complete fuzzy using alpha cut.

APA, Harvard, Vancouver, ISO, and other styles

5

Bednarz, Urszula, Iwona Włoch, and Małgorzata Wołowiec-Musiał. "Total Graph Interpretation of the Numbers of the Fibonacci Type." Journal of Applied Mathematics 2015 (2015): 1–7. http://dx.doi.org/10.1155/2015/837917.

Full text

Abstract:

We give a total graph interpretation of the numbers of the Fibonacci type. This graph interpretation relates to an edge colouring by monochromatic paths in graphs. We will show that it works for almost all numbers of the Fibonacci type. Moreover, we give the lower bound and the upper bound for the number of all(A1,2A1)-edge colourings in trees.

APA, Harvard, Vancouver, ISO, and other styles

6

JUKNA, S., and G. SCHNITGER. "Triangle-Freeness is Hard to Detect." Combinatorics, Probability and Computing 11, no. 6 (November 2002): 549–69. http://dx.doi.org/10.1017/s0963548302005333.

Full text

Abstract:

We show that recognizing the K3-freeness and K4-freeness of graphs is hard, respectively, for two-player nondeterministic communication protocols using exponentially many partitions and for nondeterministic syntactic read-r times branching programs.The key ingredient is a generalization of a colouring lemma, due to Papadimitriou and Sipser, which says that for every balanced red—blue colouring of the edges of the complete n-vertex graph there is a set of εn2 triangles, none of which is monochromatic, such that no triangle can be formed by picking edges from different triangles. We extend this lemma to exponentially many colourings and to partial colourings.

APA, Harvard, Vancouver, ISO, and other styles

7

Bard, Stefan, Gary MacGillivray, and Shayla Redlin. "The complexity of frugal colouring." Arabian Journal of Mathematics 10, no. 1 (January 29, 2021): 51–57. http://dx.doi.org/10.1007/s40065-021-00311-7.

Full text

Abstract:

AbstractA t-frugal colouring of a graph G is an assignment of colours to the vertices of G, such that each colour appears at most t times in the neighbourhood of any vertex. A dichotomy theorem for the complexity of deciding whether a graph has a 1-frugal colouring with k colours was found by McCormick and Thomas, and then later extended to restricted graph classes by Kratochvil and Siggers. We generalize the McCormick and Thomas theorem by proving a dichotomy theorem for the complexity of deciding whether a graph has a t-frugal colouring with k colours, for all pairs of positive integers t and k. We also generalize bounds of Lih et al. for the number of colours needed in a 1-frugal colouring of a given $$K_4$$ K 4 -minor-free graph with maximum degree $$\Delta $$ Δ to t-frugal colourings, for any positive integer t.

APA, Harvard, Vancouver, ISO, and other styles

8

Sudheer, Niranjana, Ann Cherian George, Achu Aniyan, and Sudev Naduvath. "Some new results on colour-induced signed graphs." Acta Universitatis Sapientiae, Informatica 14, no. 2 (December 1, 2022): 338–53. http://dx.doi.org/10.2478/ausi-2022-0019.

Full text

Abstract:

Abstract A signed graph is a graph in which positive or negative signs are assigned to its edges. We consider equitable colouring and Hamiltonian colouring to obtain induced signed graphs. An equitable colour-induced signed graph is a signed graph constructed from a given graph in which each edge uv receives a sign (−1)|c(v)−c(u)|,where c is an equitable colouring of vertex v. A Hamiltonian colour-induced signed graph is a signed graph obtained from a graph G in which for each edge e = uv, the signature function σ(uv)=(−1)|c(v)−c(u)|, gives a sign such that, |c(u)− c(v)| ≥ n − 1 − D(u, v) where c is a function that assigns a colour to each vertex satisfying the given condition. This paper discusses the properties and characteristics of signed graphs induced by the equitable and Hamiltonian colouring of graphs.

APA, Harvard, Vancouver, ISO, and other styles

9

KIERSTEAD, H. A., and A. V. KOSTOCHKA. "A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring." Combinatorics, Probability and Computing 17, no. 2 (March 2008): 265–70. http://dx.doi.org/10.1017/s0963548307008619.

Full text

Abstract:

A proper vertex colouring of a graph is equitable if the sizes of colour classes differ by at most one. We present a new shorter proof of the celebrated Hajnal–Szemerédi theorem: for every positive integer r, every graph with maximum degree at most r has an equitable colouring with r+1 colours. The proof yields a polynomial time algorithm for such colourings.

APA, Harvard, Vancouver, ISO, and other styles

10

Harary, Frank, and Zsolt Tuza. "Two graph-colouring games." Bulletin of the Australian Mathematical Society 48, no. 1 (August 1993): 141–49. http://dx.doi.org/10.1017/s0004972700015549.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Marcu, Dănuţ. "A note on graph colouring." Czechoslovak Mathematical Journal 45, no. 2 (1995): 231–33. http://dx.doi.org/10.21136/cmj.1995.128528.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Smirnov, Alexander Valeryevich. "Two-Step Colouring of Grid Graphs of Different Types." Modeling and Analysis of Information Systems 29, no. 3 (September 25, 2022): 166–80. http://dx.doi.org/10.18255/1818-1015-2022-3-166-180.

Full text

Abstract:

In this article, we consider the NP-hard problem of the two-step colouring of a graph. It is required to colour the graph in a given number of colours in a way, when no pair of vertices has the same colour, if these vertices are at a distance of 1 or 2 between each other. The optimum two-step colouring is one that uses the minimum possible number of colours.The two-step colouring problem is studied in application to grid graphs. We consider four types of grids: triangular, square, hexagonal, and octogonal. We show that the optimum two-step colouring of hexagonal and octogonal grid graphs requires 4 colours in the general case. We formulate the polynomial algorithms for such a colouring. A square grid graph with the maximum vertex degree equal to 3 requires 4 or 5 colours for a two-step colouring. In the paper, we suggest the backtracking algorithm for this case. Also, we present the algorithm, which works in linear time relative to the number of vertices, for the two-step colouring in 7 colours of a triangular grid graph and show that this colouring is always correct. If the maximum vertex degree equals 6, the solution is optimum.

APA, Harvard, Vancouver, ISO, and other styles

13

Yap, H. P., Wang Jian-Fang, and Zhang Zhongfu. "Total chromatic number of graphs of high degree." Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics 47, no. 3 (December 1989): 445–52. http://dx.doi.org/10.1017/s1446788700033176.

Full text

Abstract:

AbstractUsing a new proof technique of the first author (by adding a new vertex to a graph and creating a total colouring of the old graph from an edge colouring of the new graph), we prove that the TCC (Total Colouring Conjecture) is true for any graph G of order n having maximum degree at least n - 4. These results together with some earlier results of M. Rosenfeld and N. Vijayaditya (who proved that the TCC is true for graphs having maximum degree at most 3), and A. V. Kostochka (who proved that the TCC is true for graphs having maximum degree 4) confirm that the TCC is true for graphs whose maximum degree is either very small or very big.

APA, Harvard, Vancouver, ISO, and other styles

14

zhu, Xuding. "Circular colouring and graph homomorphism." Bulletin of the Australian Mathematical Society 59, no. 1 (February 1999): 83–97. http://dx.doi.org/10.1017/s0004972700032627.

Full text

Abstract:

For any pair of integers p, q such that (p, q) = 1 and p ≥ 2q, the graph has vertices {0, 1, …, p − 1} and edges {ij: q ≤ |i − j| ≤ p − q}. These graphs play the same role in the study of circular chromatic number as that played by the complete graphs in the study of chromatic number. The graphs share many properties of the complete graphs. However, there are also striking differences between the graphs and the complete graphs. We shall prove in this paper that for many pairs of integers p, q, one may delete most of the edges of so that the resulting graph still has circular chromatic number p/q. To be precise, we shall prove that for any number r < 2, there exists a rational number p/q (where (p, q) = 1) which is less than r but arbitrarily close to r, such that contains a subgraph H with and . This is in sharp contrast to the fact that the complete graphs are edge critical, that is, the deletion of any edge will decrease its chromatic number and its circular chromatic number.

APA, Harvard, Vancouver, ISO, and other styles

15

BERKE, R., and T. SZABÓ. "Deciding Relaxed Two-Colourability: A Hardness Jump." Combinatorics, Probability and Computing 18, no. 1-2 (March 2009): 53–81. http://dx.doi.org/10.1017/s0963548309009663.

Full text

Abstract:

We study relaxations of proper two-colourings, such that the order of the induced monochromatic components in one (or both) of the colour classes is bounded by a constant. A colouring of a graph G is called (C1, C2)-relaxed if every monochromatic component induced by vertices of the first (second) colour is of order at most C1 (C2, resp.). We prove that the decision problem ‘Is there a (1, C)-relaxed colouring of a given graph G of maximum degree 3?’ exhibits a hardness jump in the component order C. In other words, there exists an integer f(3) such that the decision problem is NP-hard for every 2 ≤ C < f(3), while every graph of maximum degree 3 is (1, f(3))-relaxed colourable. We also show f(3) ≤ 22 by way of a quasilinear time algorithm, which finds a (1, 22)-relaxed colouring of any graph of maximum degree 3. Both the bound on f(3) and the running time greatly improve earlier results. We also study the symmetric version, that is, when C1 = C2, of the relaxed colouring problem and make the first steps towards establishing a similar hardness jump.

APA, Harvard, Vancouver, ISO, and other styles

16

Sangeetha Devi, A. "An Extensive Study on Graph Colourings and Dominator Chromatic Number of Sugeno-Type Fuzzy Graphs." Mathematical Problems in Engineering 2022 (September 28, 2022): 1–7. http://dx.doi.org/10.1155/2022/3135201.

Full text

Abstract:

The concept of graph colouring has become a very active field of research that enhances many practical applications and theoretical challenges. An accurate (vertex) colouring through the condition that each vertex is whichever unaccompanied in its colour class or adjoining to all vertices of at least one colour class is known as dominator colouring. A graph is dominator colouring is a suitable colouring in which at least one vertex dominates each colour class. Many difficult and global issues are solved using fuzzy graph colouring approaches. In this paper, we introduce a new Sugeno-Type Fuzzy graph of groups, which is found using several fuzzy graph operations such as dominant path-colouring number, cycle, union, join, and products. A number that is representative based on those vertices in the formations of all paths with those vertices as their starts and ends to compare with other paths is the minimum number of shared edges based on those vertices in the formations of all paths with those vertices as their starts and ends to compare with other paths. The sugeno dominant path-colouring number is the minimum Sugeno number of shared edges among the Sugeno cardinality of all sets of shared edges, which allows for various techniques. These results are used in studying various and recently introduced chromatic numbers of graphs.

APA, Harvard, Vancouver, ISO, and other styles

17

Medvedeva, Natalya Sergeevna, and Alexander Valeryevich Smirnov. "NP-completeness and One Polynomial Subclass of the Two-Step Graph Colouring Problem." Modeling and Analysis of Information Systems 26, no. 3 (September 28, 2019): 405–19. http://dx.doi.org/10.18255/1818-1015-2019-3-405-419.

Full text

Abstract:

In this paper, we study the two-step colouring problem for an undirected connected graph. It is required to colour the graph in a given number of colours in a way, when no pair of vertices has the same colour, if these vertices are at a distance of 1 or 2 between each other. Also the corresponding recognition problem is set. The problem is closely related to the classical graph colouring problem. In the article, we study and prove the polynomial reduction of the problems to each other. So it allows us to prove NP-completeness of the problem of two-step colouring. Also we specify some of its properties. Special interest is paid to the problem of two-step colouring in application to rectangular grid graphs. The maximum vertex degree in such a graph is between 0 and 4. For each case, we elaborate and prove the function of two-vertex colouring in the minimum possible number of colours. The functions allow each vertex to be coloured independently from others. If vertices are examined in a sequence, colouring time is polynomial for a rectangular grid graph.

APA, Harvard, Vancouver, ISO, and other styles

18

Dobrev, Stefan, Heiko Schröder, Ondrej Sýkora, and Imrich Vrt'o. "Evolutionary graph colouring." Information Processing Letters 76, no. 1-2 (November 2000): 91–94. http://dx.doi.org/10.1016/s0020-0190(00)00125-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

GLEBOV, ROMAN, TIBOR SZABÓ, and GÁBOR TARDOS. "Conflict-Free Colouring of Graphs." Combinatorics, Probability and Computing 23, no. 3 (November 29, 2013): 434–48. http://dx.doi.org/10.1017/s0963548313000540.

Full text

Abstract:

We study the conflict-free chromatic number χCFof graphs from extremal and probabilistic points of view. We resolve a question of Pach and Tardos about the maximum conflict-free chromatic number ann-vertex graph can have. Our construction is randomized. In relation to this we study the evolution of the conflict-free chromatic number of the Erdős–Rényi random graphG(n,p) and give the asymptotics forp= ω(1/n). We also show that forp≥ 1/2 the conflict-free chromatic number differs from the domination number by at most 3.

APA, Harvard, Vancouver, ISO, and other styles

20

SAJITH, G., and SANJEEV SAXENA. "PARALLEL VERTEX COLOURING OF INTERVAL GRAPHS." International Journal of Foundations of Computer Science 10, no. 01 (March 1999): 19–31. http://dx.doi.org/10.1142/s0129054199000034.

Full text

Abstract:

Evidence is given to suggest that minimally vertex colouring an interval graph may not be in NC 1. This is done by showing that 3-colouring a linked list is NC 1-reducible to minimally colouring an interval graph. However, it is shown that an interval graph with a known interval representation and an O(1) chromatic number can be minimally coloured in NC 1. For the CRCW PRAM model, an o( log n) time, polynomial processors algorithm is obtained for minimally colouring an interval graph with o( log n) chromatic number and a known interval representation. In particular, when the chromatic number is O(( log n)1-ε), 0<ε<1, the algorithm runs in O( log n/ log log n) time. Also, an O( log n) time, O(n) cost, EREW PRAM algorithm is found for interval graphs of arbitrary chromatic numbers. The following lower bound result is also obtained: even when the left and right endpoints of the interval are separately sorted, minimally colouring an interval graph needs Ω( log n/ log log n) time, on a CRCW PRAM, with a polynomial number of processors.

APA, Harvard, Vancouver, ISO, and other styles

21

KITTIPASSORN, TEERADEJ, and BHARGAV P. NARAYANAN. "A Canonical Ramsey Theorem for Exactly m-Coloured Complete Subgraphs." Combinatorics, Probability and Computing 23, no. 1 (October 18, 2013): 102–15. http://dx.doi.org/10.1017/s0963548313000503.

Full text

Abstract:

Given an edge colouring of a graph with a set of m colours, we say that the graph is exactly m-coloured if each of the colours is used. We consider edge colourings of the complete graph on $\mathbb{N}$ with infinitely many colours and show that either one can find an exactly m-coloured complete subgraph for every natural number m or there exists an infinite subset X ⊂ $\mathbb{N}$ coloured in one of two canonical ways: either the colouring is injective on X or there exists a distinguished vertex v in X such that X\{v} is 1-coloured and each edge between v and X\{v} has a distinct colour (all different to the colour used on X\{v}). This answers a question posed by Stacey and Weidl in 1999. The techniques that we develop also enable us to resolve some further questions about finding exactly m-coloured complete subgraphs in colourings with finitely many colours.

APA, Harvard, Vancouver, ISO, and other styles

22

Pandey, Priyanka, and Mayamma Joseph. "Average distance colouring of graphs." Acta Universitatis Sapientiae, Informatica 15, no. 2 (December 1, 2023): 205–20. http://dx.doi.org/10.2478/ausi-2023-0014.

Full text

Abstract:

Abstract For a graph G with n vertices, average distance µ(G) is the ratio of sum of the lengths of the shortest paths between all pairs of vertices to the number of edges in a complete graph on n vertices. In this paper, we introduce average distance colouring and find the average distance colouring number of certain classes of graphs.

APA, Harvard, Vancouver, ISO, and other styles

23

KAMČEV, NINA, TOMASZ ŁUCZAK, and BENNY SUDAKOV. "Anagram-Free Colourings of Graphs." Combinatorics, Probability and Computing 27, no. 4 (August 8, 2017): 623–42. http://dx.doi.org/10.1017/s096354831700027x.

Full text

Abstract:

A sequenceSis calledanagram-freeif it contains no consecutive symbolsr1r2. . .rkrk+1. . .r2ksuch thatrk+1. . .r2kis a permutation of the blockr1r2. . .rk. Answering a question of Erdős and Brown, Keränen constructed an infinite anagram-free sequence on four symbols. Motivated by the work of Alon, Grytczuk, Hałuszczak and Riordan [2], we consider a natural generalization of anagram-free sequences for graph colourings. A colouring of the vertices of a given graphGis calledanagram-freeif the sequence of colours on any path inGis anagram-free. We call the minimal number of colours needed for such a colouring theanagram-chromaticnumber ofG.In this paper we study the anagram-chromatic number of several classes of graphs like trees, minor-free graphs and bounded-degree graphs. Surprisingly, we show that there are bounded-degree graphs (such as random regular graphs) in which anagrams cannot be avoided unless we essentially give each vertex a separate colour.

APA, Harvard, Vancouver, ISO, and other styles

24

K.Kalaiarasi and R.Divya. "Fuzzy Colouring of Interval-Valued Fuzzy Graph." International Journal of Fuzzy Mathematical Archive 14, no. 01 (2017): 47–57. http://dx.doi.org/10.22457/ijfma.v14n1a7.

Full text

Abstract:

Fuzzy graphs have revolutionized the analysis of problematic data to arrive at a better decision making power are different kinds. Among them, the interval-valued fuzzy graph in the simplest and generalized once. The main purpose of this paper is to introduce the chromatic number of an interval-valued fuzzy graph. Here working rule of an interval-valued fuzzy graph, power cut graph are discussed.

APA, Harvard, Vancouver, ISO, and other styles

25

Pandey, Priyanka, and Joseph Varghese Kureethara. "L(t, 1)-Colouring of Cycles." Mapana - Journal of Sciences 17, no. 3 (July 1, 2018): 29–42. http://dx.doi.org/10.12723/mjs.46.3.

Full text

Abstract:

For a given finite set T including zero, an L(t, 1)-colouring of a graph G is an assignment of non-negative integers to the vertices of G such that the difference between the colours of adjacent vertices must not belong to the set T and the colours of vertices that are at distance two must be distinct. For a graph G, the L(t, 1)-span of G is the minimum of the highest colour used to colour the vertices of a graph out of all the possible L(t, 1)-colourings. We study the L(t, 1)-span of cycles with respect to specific sets.

APA, Harvard, Vancouver, ISO, and other styles

26

Hujter, M., and Zs Tuza. "Precoloring Extension III: Classes of Perfect Graphs." Combinatorics, Probability and Computing 5, no. 1 (March 1996): 35–56. http://dx.doi.org/10.1017/s0963548300001826.

Full text

Abstract:

We continue the study of the following general problem on the vertex colourings of graphs. Suppose that some vertices of a graph G are assigned to some colours. Can this ‘precolouring’ be extended to a proper colouring of G with at most k colours (for some given k)? Here we investigate the complexity status of precolouring extendibility on some classes of perfect graphs, giving good characterizations (necessary and sufficient conditions) that lead to algorithms with linear or polynomial running time. It is also shown how a larger subclass of perfect graphs can be derived from graphs containing no induced path on four vertices.

APA, Harvard, Vancouver, ISO, and other styles

27

LINIAL, NATHAN, JIŘÍ MATOUŠEK, OR SHEFFET, and GÁBOR TARDOS. "Graph Colouring with No Large Monochromatic Components." Combinatorics, Probability and Computing 17, no. 4 (July 2008): 577–89. http://dx.doi.org/10.1017/s0963548308009140.

Full text

Abstract:

For a graph G and an integer t we let mcct(G) be the smallest m such that there exists a colouring of the vertices of G by t colours with no monochromatic connected subgraph having more than m vertices. Let be any non-trivial minor-closed family of graphs. We show that mcc2(G) = O(n2/3) for any n-vertex graph G ∈ . This bound is asymptotically optimal and it is attained for planar graphs. More generally, for every such , and every fixed t we show that mcct(G)=O(n2/(t+1)). On the other hand, we have examples of graphs G with no Kt+3 minor and with mcct(G)=Ω(n2/(2t−1)).It is also interesting to consider graphs of bounded degrees. Haxell, Szabó and Tardos proved mcc2(G) ≤ 20000 for every graph G of maximum degree 5. We show that there are n-vertex 7-regular graphs G with mcc2(G)=Ω(n), and more sharply, for every ϵ > 0 there exists cϵ > 0 and n-vertex graphs of maximum degree 7, average degree at most 6 + ϵ for all subgraphs, and with mcc2(G) ≥ cϵn. For 6-regular graphs it is known only that the maximum order of magnitude of mcc2 is between $\sqrt n$ and n.We also offer a Ramsey-theoretic perspective of the quantity mcct(G).

APA, Harvard, Vancouver, ISO, and other styles

28

Everett, Martin G., and Steve Borgatti. "Role colouring a graph." Mathematical Social Sciences 21, no. 2 (April 1991): 183–88. http://dx.doi.org/10.1016/0165-4896(91)90080-b.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Hind, Hugh, Michael Molloy, and Bruce Reed. "Colouring a graph frugally." Combinatorica 17, no. 4 (December 1997): 469–82. http://dx.doi.org/10.1007/bf01195001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Kayll, P. Mark, and Michael Morris. "On Colouring Oriented Graphs of Large Girth." Contributions to Discrete Mathematics 18, no. 2 (December 31, 2023): 234–43. http://dx.doi.org/10.55016/ojs/cdm.v18i2.73457.

Full text

Abstract:

We prove that for every oriented graph $D$ and every choice of positive integers $k$ and $\ell$, there exists an oriented graph $D^*$ along with a surjective homomorphism $\psi\colon D^* \to D$ such that: (i) girth$(D^*) \geq\ell$; (ii) for every oriented graph $C$ with at most $k$ vertices, there exists a homomorphism from $D^*$ to $C$ if and only if there exists a homomorphism from $D$ to C; and (iii) for every $D$-pointed oriented graph $C$ with at most $k$ vertices and for every homomorphism $\varphi\colon D^* \to C$ there exists a unique homomorphism $f\colon D \to C$ such that $\varphi=f \circ \psi$. Determining the chromatic number of an oriented graph $D$ is equivalent to finding the smallest integer $k$ such that $D$ admits a homomorphism to an order-$k$ tournament, so our main theorem yields results on the girth and chromatic number of oriented graphs. While our main proof is probabilistic (hence nonconstructive), for any given $\ell\geq 3$ and $k\geq 5$, we include a construction of an oriented graph with girth $\ell$ and chromatic number $k$.

APA, Harvard, Vancouver, ISO, and other styles

31

Arifin, Samsul, Indra Bayu Muktyas, and Jeremy Matthew Mandei. "Graph coloring program for variation of exam scheduling modeling at Binus University based on Welsh and Powell algorithm." Journal of Physics: Conference Series 2279, no. 1 (May 1, 2022): 012005. http://dx.doi.org/10.1088/1742-6596/2279/1/012005.

Full text

Abstract:

Abstract In this article, we will design a computer program to solve graph colouring and to visualize the variation of exam scheduling modelling at Binus University in graphs based on the Welch and Powell Algorithm. A vertex colouring of graph G = (V, E) is an F: V → N mapping where the adjacent vertex are different colours in N, i.e. if the edge (u, v) are in E, then F (u) is not equal to F (v). The formulation of problems regarding computer programs based on a small experiment and variations in modelling exams is carried out in graph form using the Visual Basic Application.

APA, Harvard, Vancouver, ISO, and other styles

32

Dorfling, Samantha, and Tomáš Vetrík. "Edge-colouring of graphs and hereditary graph properties." Czechoslovak Mathematical Journal 66, no. 1 (March 2016): 87–99. http://dx.doi.org/10.1007/s10587-016-0241-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Ganesan, Ghurumuruhan. "Acyclic and tree unique colourings in random graphs." Gulf Journal of Mathematics 16, no. 2 (April 12, 2024): 27–38. http://dx.doi.org/10.56947/gjom.v16i2.1867.

Full text

Abstract:

In this paper we study acyclic colouring in the random subgraph G of the complete graph Kn on n vertices where each edge is present with probability p, independent of the other edges. We show that unlike the ordinary chromatic number, the acyclic chromatic number exhibits a phase transition from sub-linear to linear growth as the edge probability increases, even in the sparse regime and obtain estimates for the critical exponent. We show that allowing for a small relaxation in the acyclic colouring condition allows for sublinear growth for all values of the edge probability exponent. We also study a generalization of unique colourings where we impose the condition that at least one vertex in any copy of a given tree has a unique colour and obtain bounds for the minimum number of colours needed for such a colouring.

APA, Harvard, Vancouver, ISO, and other styles

34

Sotskov, Yuri N. "Mixed graph colouring as scheduling multi-processor tasks with equal processing times." Journal of the Belarusian State University. Mathematics and Informatics, no. 2 (August 5, 2021): 67–81. http://dx.doi.org/10.33581/2520-6508-2021-2-67-81.

Full text

Abstract:

A problem of scheduling partially ordered unit-time tasks processed on dedicated machines is formulated as a mixed graph colouring problem, i. e., as an assignment of integers (colours) {1, 2, …, t} to the vertices (tasks) V {ν1, ν2, …, νn}, of the mixed graph G = (V, A, E) such that if vertices vp and vq are joined by an edge [νp, νq] ∈ E their colours have to be different. Further, if two vertices νp and νq are joined by an arc (νi, νj) ∈ A the colour of vertex νi has to be no greater than the colour of vertex νj. We prove that an optimal colouring of a mixed graph G = (V, A, E) is equivalent to the scheduling problem GcMPT|pi = 1|Cmax of finding an optimal schedule for partially ordered multi-processor tasks with unit (equal) processing times. Contrary to classical shop-scheduling problems, several dedicated machines are required to process an individual task in the scheduling problem GcMPT|pi = 1|Cmax. Moreover, along with precedence constraints given on the set V {ν1, ν2, …, νn}, it is required that a subset of tasks must be processed simultaneously. Due to the theorems proved in this article, most analytical results that have been proved for the scheduling problems GcMPT |pi = 1|Cmax so far, have analogous results for optimal colourings of the mixed graphs G = (V, A, E), and vice versa.

APA, Harvard, Vancouver, ISO, and other styles

35

LEVIN, LEONID A., and RAMARATHNAM VENKATESAN. "An Average Case NP-complete Graph Colouring Problem." Combinatorics, Probability and Computing 27, no. 5 (April 2, 2018): 808–28. http://dx.doi.org/10.1017/s0963548318000123.

Full text

Abstract:

NP-complete problems should be hard on some instances but those may be extremely rare. On generic instances many such problems, especially related to random graphs, have been proved to be easy. We show the intractability of random instances of a graph colouring problem: this graph problem is hard on average unless all NP problems under all samplable (i.e. generatable in polynomial time) distributions are easy. Worst case reductions use special gadgets and typically map instances into a negligible fraction of possible outputs. Ours must output nearly random graphs and avoid any super-polynomial distortion of probabilities. This poses significant technical difficulties.

APA, Harvard, Vancouver, ISO, and other styles

36

Mohammad, Husam Qasem, Shaymaa Haleem Ibrahem, and Luma Ahmed Khaleel. "The Metric Chromatic Number of Zero Divisor Graph of a Ring Z n." International Journal of Mathematics and Mathematical Sciences 2022 (September 27, 2022): 1–4. http://dx.doi.org/10.1155/2022/9069827.

Full text

Abstract:

Let Γ be a nontrivial connected graph, c : V Γ ⟶ ℕ be a vertex colouring of Γ , and L i be the colouring classes that resulted, where i = 1,2 , … , k . A metric colour code for a vertex a of a graph Γ is c a = d a , L 1 , d a , L 2 , … , d a , L n , where d a , L i is the minimum distance between vertex a and vertex b in L i . If c a ≠ c b , for any adjacent vertices a and b of Γ , then c is called a metric colouring of Γ as well as the smallest number k satisfies this definition which is said to be the metric chromatic number of a graph Γ and symbolized μ Γ . In this work, we investigated a metric colouring of a graph Γ Z n and found the metric chromatic number of this graph, where Γ Z n is the zero-divisor graph of ring Z n .

APA, Harvard, Vancouver, ISO, and other styles

37

šKREKOVSKI, R. "A Grötzsch-Type Theorem for List Colourings with Impropriety One." Combinatorics, Probability and Computing 8, no. 5 (September 1999): 493–507. http://dx.doi.org/10.1017/s096354839900396x.

Full text

Abstract:

A graph G is m-choosable with impropriety d, or simply (m, d)*-choosable, if, for every list assignment L, where [mid ]L(v)[mid ][ges ]m for every v∈V(G), there exists an L-colouring of G such that each vertex of G has at most d neighbours coloured with the same colour as itself. We prove a Grötzsch-type theorem for list colourings with impropriety one, that is, the (3, 1)*-choosability for triangle-free planar graphs; in the proof the method of extending a precolouring of a 4- or 5-cycle is used.

APA, Harvard, Vancouver, ISO, and other styles

38

Hàn, Hiêp, Troy Retter, Vojtêch Rödl, and Mathias Schacht. "Ramsey-type numbers involving graphs and hypergraphs with large girth." Combinatorics, Probability and Computing 30, no. 5 (April 12, 2021): 722–40. http://dx.doi.org/10.1017/s0963548320000383.

Full text

Abstract:

AbstractErdős asked if, for every pair of positive integers g and k, there exists a graph H having girth (H) = k and the property that every r-colouring of the edges of H yields a monochromatic cycle Ck. The existence of such graphs H was confirmed by the third author and Ruciński.We consider the related numerical problem of estimating the order of the smallest graph H with this property for given integers r and k. We show that there exists a graph H on R10k2; k15k3 vertices (where R = R(Ck; r) is the r-colour Ramsey number for the cycle Ck) having girth (H) = k and the Ramsey property that every r-colouring of the edges of H yields a monochromatic Ck Two related numerical problems regarding arithmetic progressions in subsets of the integers and cliques in graphs are also considered.

APA, Harvard, Vancouver, ISO, and other styles

39

SEN SARMA, S., and S. K. BANDYOPADHYAY. "Some sequential graph colouring algorithms." International Journal of Electronics 67, no. 2 (August 1989): 187–99. http://dx.doi.org/10.1080/00207218908921070.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

NOLTE, ANDREAS, and RAINER SCHRADER. "Simulated Annealing and Graph Colouring." Combinatorics, Probability and Computing 10, no. 1 (January 2001): 29–40. http://dx.doi.org/10.1017/s0963548300004557.

Full text

Abstract:

Simulated annealing is a very successful heuristic for various problems in combinatorial optimization. In this paper an application of simulated annealing to the 3-colouring problem is considered. In contrast to many good empirical results we will show for a certain class of graphs that the expected first hitting time of a proper colouring, given an arbitrary cooling scheme, is of exponential size.These results are complementary to those in [13], where we prove the convergence of simulated annealing to an optimal solution in exponential time.

APA, Harvard, Vancouver, ISO, and other styles

41

Jensen, T. R., and B. Toft. "25 Pretty graph colouring problems." Discrete Mathematics 229, no. 1-3 (February 2001): 167–69. http://dx.doi.org/10.1016/s0012-365x(00)00206-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Cochand, Maurice, and Gyula Károlyi. "On a graph colouring problem." Discrete Mathematics 194, no. 1-3 (January 1999): 249–52. http://dx.doi.org/10.1016/s0012-365x(98)00060-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

D’Hondt, Ellie. "Quantum approaches to graph colouring." Theoretical Computer Science 410, no. 4-5 (February 2009): 302–9. http://dx.doi.org/10.1016/j.tcs.2008.09.055.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Korst, Jan, Emile Aarts, Jan Karel Lenstra, and Jaap Wessels. "Periodic assignment and graph colouring." Discrete Applied Mathematics 51, no. 3 (July 1994): 291–305. http://dx.doi.org/10.1016/0166-218x(92)00036-l.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Cicuta, Giovanni M., Luca Molinari, and Emilio Montaldi. "Matrix models and graph colouring." Physics Letters B 306, no. 3-4 (June 1993): 245–51. http://dx.doi.org/10.1016/0370-2693(93)90075-s.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Caro, Y., and Y. Roditty. "On zero-sum turan problems of Bialostocki and Dierker." Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics 53, no. 3 (December 1992): 402–7. http://dx.doi.org/10.1017/s1446788700036569.

Full text

Abstract:

AbstractAssume G is a graph with m edges. By T(n, G) we denote the classical Turan number, namely, the maximum possible number of edges in a graph H on n vertices without a copy of G. Similarly if G is a family of graphs then H does not have a copy of any member of the family. A Zk-colouring of a graph G is a colouring of the edges of G by Zk, the additive group of integers modulo k, avoiding a copy of a given graph H, for which the sum of the values on its edges is 0 (mod k). By the Zero-Sum Turan number, denoted T(n, G, Zk), k¦m, we mean the maximum number of edges in a Zk-colouring of a graph on n vertices that contains no zero-sum (mod k) copy of G. Here we mainly solve two problems of Bialostocki and Dierker [6].Problem 1. Determine T(n, tK2, Zk) for ¦|t. In particular, is it true that T(n, tK2, Zk) = T(n, (t+k-1)K2)?Problem 2. Does there exist a constant c(t, k) such that T(n, Ft, Zk) ≦ c(t, k)n, where Ft is the family of cycles of length at least t?

APA, Harvard, Vancouver, ISO, and other styles

47

Ma, Yingbin, and Kairui Nie. "Rainbow Vertex Connection Numbers and Total Rainbow Connection Numbers of Middle and Total Graphs." Ars Combinatoria 157 (December 31, 2023): 45–52. http://dx.doi.org/10.61091/ars157-04.

Full text

Abstract:

A vertex-colouring of a graph Γ is rainbow vertex connected if every pair of vertices ( u , v ) in Γ there is a u − v path whose internal vertices have different colours. The rainbow vertex connection number of a graph Γ , is the minimum number of colours needed to make Γ rainbow vertex connected, denoted by r v c ( Γ ) . Here, we study the rainbow vertex connection numbers of middle and total graphs. A total-colouring of a graph Γ is total rainbow connected if every pair of vertices ( u , v ) in Γ there is a u − v path whose edges and internal vertices have different colours. The total rainbow connection number of Γ , is the minimum number of colours required to colour the edges and vertices of Γ in order to make Γ total rainbow connected, denoted by t r c ( Γ ) . In this paper, we also research the total rainbow connection numbers of middle and total graphs.

APA, Harvard, Vancouver, ISO, and other styles

48

Tosuni, Besjana. "Graph Coloring Problems in Modern Computer Science." European Journal of Interdisciplinary Studies 1, no. 2 (August 30, 2015): 87. http://dx.doi.org/10.26417/ejis.v1i2.p87-95.

Full text

Abstract:

Graph coloring is one of the most important concepts in graph theory and is used in many real time applications in computer science. The main aim of this paper is to present the importance of graph coloring ideas in various areas of compute applications for researches that they can use graph coloring concepts for the research. Graph coloring used in various research areas of computer science such data mining, image segmentation, clustering, image capturing, networking etc. This papers mainly focused on important applications such as Guarding an Art Gallery, Physical layout segmentation, Round-Robin Sports Scheduling, Aircraft scheduling, Biprocessor tasks, Frequency assignment, Final Exam Timetabling as a Grouping Problem, Map coloring and GSM mobile phone networks, and Student Time Table. In this paper we review several variants of graph colouring, such as precolouring extension, list colouring, multicolouring, minimum sum colouring, and discuss their applications in scheduling. A very important graph parameter is the chromatic number. Presently, graph coloring plays an important role in several real-world applications and still engages exciting research.

APA, Harvard, Vancouver, ISO, and other styles

49

Tosuni, Besjana. "Graph Coloring Problems in Modern Computer Science." European Journal of Interdisciplinary Studies 2, no. 1 (August 30, 2015): 87. http://dx.doi.org/10.26417/ejis.v2i1.p87-95.

Full text

Abstract:

Graph coloring is one of the most important concepts in graph theory and is used in many real time applications in computer science. The main aim of this paper is to present the importance of graph coloring ideas in various areas of compute applications for researches that they can use graph coloring concepts for the research. Graph coloring used in various research areas of computer science such data mining, image segmentation, clustering, image capturing, networking etc. This papers mainly focused on important applications such as Guarding an Art Gallery, Physical layout segmentation, Round-Robin Sports Scheduling, Aircraft scheduling, Biprocessor tasks, Frequency assignment, Final Exam Timetabling as a Grouping Problem, Map coloring and GSM mobile phone networks, and Student Time Table. In this paper we review several variants of graph colouring, such as precolouring extension, list colouring, multicolouring, minimum sum colouring, and discuss their applications in scheduling. A very important graph parameter is the chromatic number. Presently, graph coloring plays an important role in several real-world applications and still engages exciting research.

APA, Harvard, Vancouver, ISO, and other styles

50

Marsidi, Marsidi, and Ika Hesti Agustin. "The local antimagic on disjoint union of some family graphs." Jurnal Matematika "MANTIK" 5, no. 2 (October 27, 2019): 69–75. http://dx.doi.org/10.15642/mantik.2019.5.2.69-75.

Full text

Abstract:

A graph in this paper is nontrivial, finite, connected, simple, and undirected. Graph consists of a vertex set and edge set. Let u,v be two elements in vertex set, and q is the cardinality of edge set in G, a bijective function from the edge set to the first q natural number is called a vertex local antimagic edge labelling if for any two adjacent vertices and , the weight of is not equal with the weight of , where the weight of (denoted by ) is the sum of labels of edges that are incident to . Furthermore, any vertex local antimagic edge labelling induces a proper vertex colouring on where is the colour on the vertex . The vertex local antimagic chromatic number is the minimum number of colours taken over all colourings induced by vertex local antimagic edge labelling of . In this paper, we discuss about the vertex local antimagic chromatic number on disjoint union of some family graphs, namely path, cycle, star, and friendship, and also determine the lower bound of vertex local antimagic chromatic number of disjoint union graphs. The chromatic numbers of disjoint union graph in this paper attend the lower bound.

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!