Log in

Relevant bibliographies by topics / Coloriage de graphe / Journal articles

To see the other types of publications on this topic, follow the link: Coloriage de graphe.

Journal articles on the topic 'Coloriage de graphe'

Author: Grafiati

Published: 4 June 2021

Last updated: 11 February 2022

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 'Coloriage de graphe.'

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

Bagheri Gh., Behrooz, and Behnaz Omoomi. "On the simultaneous edge coloring of graphs." Discrete Mathematics, Algorithms and Applications 06, no. 04 (October 10, 2014): 1450049. http://dx.doi.org/10.1142/s1793830914500499.

Full text

Abstract:

A μ-simultaneous edge coloring of graph G is a set of μ proper edge colorings of G with a same color set such that for each vertex, the sets of colors appearing on the edges incident to that vertex are the same in each coloring and no edge receives the same color in any two colorings. The μ-simultaneous edge coloring of bipartite graphs has a close relation with μ-way Latin trades. Mahdian et al. (2000) conjectured that every bridgeless bipartite graph is 2-simultaneous edge colorable. Luo et al. (2004) showed that every bipartite graphic sequence S with all its elements greater than one, has a realization that admits a 2-simultaneous edge coloring. In this paper, the μ-simultaneous edge coloring of graphs is studied. Moreover, the properties of the extremal counterexample to the above conjecture are investigated. Also, a relation between 2-simultaneous edge coloring of a graph and a cycle double cover with certain properties is shown and using this relation, some results about 2-simultaneous edge colorable graphs are obtained.

APA, Harvard, Vancouver, ISO, and other styles

2

Abhishek, Kumar. "Strongly set-colorable graphs." Discrete Mathematics, Algorithms and Applications 11, no. 01 (February 2019): 1950007. http://dx.doi.org/10.1142/s1793830919500071.

Full text

Abstract:

In [S. M. Hegde, Set colorings of graphs, European J. Combin. 30 (2009) 986–995.] Hegde introduced the notion of set colorings of a graph [Formula: see text] as an assignment of distinct subsets of a finite set [Formula: see text] of [Formula: see text] colors to the vertices of [Formula: see text] such that all the colors of the edges which are obtained as the symmetric differences of the subsets assigned to their end-vertices are distinct. Additionally, if all the sets on the vertices and edges of [Formula: see text] are the set of all nonempty subsets of [Formula: see text] then the coloring is said to be a strong set-coloring and [Formula: see text] is said to be strongly set-colorable. In this paper, we report some new necessary conditions and propose a conjuncture for the sufficient condition for a graph to admit strong set-coloring. We also identify and characterize some new classes of graphs admitting strong set-coloring. In addition to these, we also propose strategies to construct infinite families graphs admitting strong set-coloring.

APA, Harvard, Vancouver, ISO, and other styles

3

Erzurumluoğlu, Aras, and C. A. Rodger. "On Evenly-Equitable, Balanced Edge-Colorings and Related Notions." International Journal of Combinatorics 2015 (March 4, 2015): 1–7. http://dx.doi.org/10.1155/2015/201427.

Full text

Abstract:

A graph G is said to be even if all vertices of G have even degree. Given a k-edge-coloring of a graph G, for each color i∈Zk={0,1,…,k-1} let G(i) denote the spanning subgraph of G in which the edge-set contains precisely the edges colored i. A k-edge-coloring of G is said to be an even k-edge-coloring if for each color i∈Zk, G(i) is an even graph. A k-edge-coloring of G is said to be evenly-equitable if for each color i∈Zk, G(i) is an even graph, and for each vertex v∈V(G) and for any pair of colors i,j∈Zk, |degG(i)(v)-degG(j)(v)|∈{0,2}. For any pair of vertices {v,w} let mG({v,w}) be the number of edges between v and w in G (we allow v=w, where {v,v} denotes a loop incident with v). A k-edge-coloring of G is said to be balanced if for all pairs of colors i and j and all pairs of vertices v and w (possibly v=w), |mG(i)({v,w})-mG(j)({v,w})|≤1. Hilton proved that each even graph has an evenly-equitable k-edge-coloring for each k∈N. In this paper we extend this result by finding a characterization for graphs that have an evenly-equitable, balanced k-edge-coloring for each k∈N. Correspondingly we find a characterization for even graphs to have an evenly-equitable, balanced 2-edge-coloring. Then we give an instance of how evenly-equitable, balanced edge-colorings can be used to determine if a certain fairness property of factorizations of some regular graphs is satisfied. Finally we indicate how different fairness notions on edge-colorings interact with each other.

APA, Harvard, Vancouver, ISO, and other styles

4

Dobrinen, Natasha. "The Ramsey theory of the universal homogeneous triangle-free graph." Journal of Mathematical Logic 20, no. 02 (January 28, 2020): 2050012. http://dx.doi.org/10.1142/s0219061320500129.

Full text

Abstract:

The universal homogeneous triangle-free graph, constructed by Henson [A family of countable homogeneous graphs, Pacific J. Math. 38(1) (1971) 69–83] and denoted [Formula: see text], is the triangle-free analogue of the Rado graph. While the Ramsey theory of the Rado graph has been completely established, beginning with Erdős–Hajnal–Posá [Strong embeddings of graphs into coloured graphs, in Infinite and Finite Sets. Vol.[Formula: see text] , eds. A. Hajnal, R. Rado and V. Sós, Colloquia Mathematica Societatis János Bolyai, Vol. 10 (North-Holland, 1973), pp. 585–595] and culminating in work of Sauer [Coloring subgraphs of the Rado graph, Combinatorica 26(2) (2006) 231–253] and Laflamme–Sauer–Vuksanovic [Canonical partitions of universal structures, Combinatorica 26(2) (2006) 183–205], the Ramsey theory of [Formula: see text] had only progressed to bounds for vertex colorings [P. Komjáth and V. Rödl, Coloring of universal graphs, Graphs Combin. 2(1) (1986) 55–60] and edge colorings [N. Sauer, Edge partitions of the countable triangle free homogenous graph, Discrete Math. 185(1–3) (1998) 137–181]. This was due to a lack of broadscale techniques. We solve this problem in general: For each finite triangle-free graph [Formula: see text], there is a finite number [Formula: see text] such that for any coloring of all copies of [Formula: see text] in [Formula: see text] into finitely many colors, there is a subgraph of [Formula: see text] which is again universal homogeneous triangle-free in which the coloring takes no more than [Formula: see text] colors. This is the first such result for a homogeneous structure omitting copies of some nontrivial finite structure. The proof entails developments of new broadscale techniques, including a flexible method for constructing trees which code [Formula: see text] and the development of their Ramsey theory.

APA, Harvard, Vancouver, ISO, and other styles

5

Fekete, Sándor P., and Phillip Keldenich. "Conflict-Free Coloring of Intersection Graphs." International Journal of Computational Geometry & Applications 28, no. 03 (September 2018): 289–307. http://dx.doi.org/10.1142/s0218195918500085.

Full text

Abstract:

A conflict-free[Formula: see text]-coloring of a graph [Formula: see text] assigns one of [Formula: see text] different colors to some of the vertices such that, for every vertex [Formula: see text], there is a color that is assigned to exactly one vertex among [Formula: see text] and [Formula: see text]’s neighbors. Such colorings have applications in wireless networking, robotics, and geometry, and are well studied in graph theory. Here we study the conflict-free coloring of geometric intersection graphs. We demonstrate that the intersection graph of [Formula: see text] geometric objects without fatness properties and size restrictions may have conflict-free chromatic number in [Formula: see text] and in [Formula: see text] for disks or squares of different sizes; it is known for general graphs that the worst case is in [Formula: see text]. For unit-disk intersection graphs, we prove that it is NP-complete to decide the existence of a conflict-free coloring with one color; we also show that six colors always suffice, using an algorithm that colors unit disk graphs of restricted height with two colors. We conjecture that four colors are sufficient, which we prove for unit squares instead of unit disks. For interval graphs, we establish a tight worst-case bound of two.

APA, Harvard, Vancouver, ISO, and other styles

6

Naduvath, Sudev. "Equitable coloring parameters of certain graph classes." Discrete Mathematics, Algorithms and Applications 10, no. 03 (June 2018): 1850040. http://dx.doi.org/10.1142/s1793830918500404.

Full text

Abstract:

Coloring the vertices of a graph [Formula: see text] subject to given conditions can be considered as a random experiment and corresponding to this experiment, a discrete random variable [Formula: see text] can be defined as the color of a vertex chosen at random, with respect to the given type of coloring of [Formula: see text] and a probability mass function for this random variable can be defined accordingly. A proper coloring [Formula: see text] of a graph [Formula: see text], which assigns colors to the vertices of [Formula: see text] such that the numbers of vertices in any two color classes differ by at most one, is called an equitable coloring of [Formula: see text]. In this paper, we study two statistical parameters of certain graphs, with respect to their equitable colorings.

APA, Harvard, Vancouver, ISO, and other styles

7

Bhakta, Prateek, Benjamin Brett Buckner, Lauren Farquhar, Vikram Kamat, Sara Krehbiel, and Heather M. Russell. "Cut-Colorings in Coloring Graphs." Graphs and Combinatorics 35, no. 1 (November 28, 2018): 239–48. http://dx.doi.org/10.1007/s00373-018-1985-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Sotskov, Yuri N. "Mixed Graph Colorings: A Historical Review." Mathematics 8, no. 3 (March 9, 2020): 385. http://dx.doi.org/10.3390/math8030385.

Full text

Abstract:

This paper presents a historical review and recent developments in mixed graph colorings in the light of scheduling problems with the makespan criterion. A mixed graph contains both a set of arcs and a set of edges. Two types of colorings of the vertices of the mixed graph and one coloring of the arcs and edges of the mixed graph have been considered in the literature. The unit-time scheduling problem with the makespan criterion may be interpreted as an optimal coloring of the vertices of a mixed graph, where the number of used colors is minimum. Complexity results for optimal colorings of the mixed graph are systematized. The published algorithms for finding optimal mixed graph colorings are briefly surveyed. Two new colorings of a mixed graph are introduced.

APA, Harvard, Vancouver, ISO, and other styles

9

KIM, DONG HAN, and SEONHEE LIM. "Subword complexity and Sturmian colorings of regular trees." Ergodic Theory and Dynamical Systems 35, no. 2 (August 13, 2013): 461–81. http://dx.doi.org/10.1017/etds.2013.50.

Full text

Abstract:

AbstractIn this article, we discuss subword complexity of colorings of regular trees. We characterize colorings of bounded subword complexity and study Sturmian colorings, which are colorings of minimal unbounded subword complexity. We classify Sturmian colorings using their type sets. We show that any Sturmian coloring is a lifting of a coloring on a quotient graph of the tree which is a geodesic or a ray, with loops possibly attached, thus a lifting of an ‘infinite word’. We further give a complete characterization of the quotient graph for eventually periodic colorings.

APA, Harvard, Vancouver, ISO, and other styles

10

Kaveh, Kamran, Alex McAvoy, Krishnendu Chatterjee, and Martin A. Nowak. "The Moran process on 2-chromatic graphs." PLOS Computational Biology 16, no. 11 (November 5, 2020): e1008402. http://dx.doi.org/10.1371/journal.pcbi.1008402.

Full text

Abstract:

Resources are rarely distributed uniformly within a population. Heterogeneity in the concentration of a drug, the quality of breeding sites, or wealth can all affect evolutionary dynamics. In this study, we represent a collection of properties affecting the fitness at a given location using a color. A green node is rich in resources while a red node is poorer. More colors can represent a broader spectrum of resource qualities. For a population evolving according to the birth-death Moran model, the first question we address is which structures, identified by graph connectivity and graph coloring, are evolutionarily equivalent. We prove that all properly two-colored, undirected, regular graphs are evolutionarily equivalent (where “properly colored” means that no two neighbors have the same color). We then compare the effects of background heterogeneity on properly two-colored graphs to those with alternative schemes in which the colors are permuted. Finally, we discuss dynamic coloring as a model for spatiotemporal resource fluctuations, and we illustrate that random dynamic colorings often diminish the effects of background heterogeneity relative to a proper two-coloring.

APA, Harvard, Vancouver, ISO, and other styles

11

McATEE, JENELLE, DANIEL S. SILVER, and SUSAN G. WILLIAMS. "COLORING SPATIAL GRAPHS." Journal of Knot Theory and Its Ramifications 10, no. 01 (February 2001): 109–20. http://dx.doi.org/10.1142/s0218216501000755.

Full text

Abstract:

Coloring invariants for spatial graphs are defined, inspired by Fox colorings of knots and links. A new proof of a the nontriviality of Suzuki's n-theta curves is given. Necessary and sufficient conditions for colorings of θn-curves are described in terms of an Alexander polynomial defined by Litherland.

APA, Harvard, Vancouver, ISO, and other styles

12

Slamin, Slamin, Nelly Oktavia Adiwijaya, Muhammad Ali Hasan, Dafik Dafik, and Kristiana Wijaya. "Local Super Antimagic Total Labeling for Vertex Coloring of Graphs." Symmetry 12, no. 11 (November 7, 2020): 1843. http://dx.doi.org/10.3390/sym12111843.

Full text

Abstract:

Let G=(V,E) be a graph with vertex set V and edge set E. A local antimagic total vertex coloring f of a graph G with vertex-set V and edge-set E is an injective map from V∪E to {1,2,…,|V|+|E|} such that if for each uv∈E(G) then w(u)≠w(v), where w(u)=∑uv∈E(G)f(uv)+f(u). If the range set f satisfies f(V)={1,2,…,|V|}, then the labeling is said to be local super antimagic total labeling. This labeling generates a proper vertex coloring of the graph G with the color w(v) assigning the vertex v. The local super antimagic total chromatic number of graph G, χlsat(G) is defined as the least number of colors that are used for all colorings generated by the local super antimagic total labeling of G. In this paper we investigate the existence of the local super antimagic total chromatic number for some particular classes of graphs such as a tree, path, cycle, helm, wheel, gear, sun, and regular graphs as well as an amalgamation of stars and an amalgamation of wheels.

APA, Harvard, Vancouver, ISO, and other styles

13

Goddard, Wayne, and Robert Melville. "Coloring subgraphs with restricted amounts of hues." Open Mathematics 15, no. 1 (September 22, 2017): 1171–80. http://dx.doi.org/10.1515/math-2017-0098.

Full text

Abstract:

Abstract We consider vertex colorings where the number of colors given to specified subgraphs is restricted. In particular, given some fixed graph F and some fixed set A of positive integers, we consider (not necessarily proper) colorings of the vertices of a graph G such that, for every copy of F in G, the number of colors it receives is in A. This generalizes proper colorings, defective coloring, and no-rainbow coloring, inter alia. In this paper we focus on the case that A is a singleton set. In particular, we investigate the colorings where the graph F is a star or is 1-regular.

APA, Harvard, Vancouver, ISO, and other styles

14

Saha, Laxman, and Pratima Panigrahi. "A new graph radio k-coloring algorithm." Discrete Mathematics, Algorithms and Applications 11, no. 01 (February 2019): 1950005. http://dx.doi.org/10.1142/s1793830919500058.

Full text

Abstract:

Due to the rapid growth in the use of wireless communication services and the corresponding scarcity and the high cost of radio spectrum bandwidth, Channel assignment problem (CAP) is becoming highly important. Radio [Formula: see text]-coloring of graphs is a variation of CAP. For a positive integer [Formula: see text], a radio [Formula: see text]-coloring of a simple connected graph [Formula: see text] is a mapping [Formula: see text] from the vertex set [Formula: see text] to the set [Formula: see text] of non-negative integers such that [Formula: see text] for each pair of distinct vertices [Formula: see text] and [Formula: see text] of [Formula: see text], where [Formula: see text] is the distance between [Formula: see text] and [Formula: see text] in [Formula: see text]. The span of a radio [Formula: see text]-coloring [Formula: see text], denoted by [Formula: see text], is defined as [Formula: see text] and the radio[Formula: see text]-chromatic number of [Formula: see text], denoted by [Formula: see text], is [Formula: see text] where the minimum is taken over all radio [Formula: see text]-coloring of [Formula: see text]. In this paper, we present two radio [Formula: see text]-coloring algorithms for general graphs which will produce radio [Formula: see text]-colorings with their spans. For an [Formula: see text]-vertex simple connected graph the time complexity of the both algorithm is of [Formula: see text]. Implementing these algorithms we get the exact value of [Formula: see text] for several graphs (for example, [Formula: see text], [Formula: see text], [Formula: see text], some circulant graph etc.) and many values of [Formula: see text], especially for [Formula: see text].

APA, Harvard, Vancouver, ISO, and other styles

15

Gurski, Frank, Dominique Komander, and Carolin Rehs. "Oriented Coloring on Recursively Defined Digraphs." Algorithms 12, no. 4 (April 25, 2019): 87. http://dx.doi.org/10.3390/a12040087.

Full text

Abstract:

Coloring is one of the most famous problems in graph theory. The coloring problem on undirected graphs has been well studied, whereas there are very few results for coloring problems on directed graphs. An oriented k-coloring of an oriented graph G = ( V , A ) is a partition of the vertex set V into k independent sets such that all the arcs linking two of these subsets have the same direction. The oriented chromatic number of an oriented graph G is the smallest k such that G allows an oriented k-coloring. Deciding whether an acyclic digraph allows an oriented 4-coloring is NP-hard. It follows that finding the chromatic number of an oriented graph is an NP-hard problem, too. This motivates to consider the problem on oriented co-graphs. After giving several characterizations for this graph class, we show a linear time algorithm which computes an optimal oriented coloring for an oriented co-graph. We further prove how the oriented chromatic number can be computed for the disjoint union and order composition from the oriented chromatic number of the involved oriented co-graphs. It turns out that within oriented co-graphs the oriented chromatic number is equal to the length of a longest oriented path plus one. We also show that the graph isomorphism problem on oriented co-graphs can be solved in linear time.

APA, Harvard, Vancouver, ISO, and other styles

16

Miro, Eden Delight, Aliw-iw Zambrano, and Agnes Garciano. "Construction of weavings in the plane." Acta Crystallographica Section A Foundations and Advances 74, no. 1 (January 1, 2018): 25–35. http://dx.doi.org/10.1107/s205327331701422x.

Full text

Abstract:

This work develops, in graph-theoretic terms, a methodology for systematically constructing weavings of overlapping nets derived from 2-colorings of the plane. From a 2-coloring, two disjoint simple, connected graphs called nets are constructed. The union of these nets forms an overlapping net, and a weaving map is defined on the intersection points of the overlapping net to form a weaving. Furthermore, a procedure is given for the construction of mixed overlapping nets and for deriving weavings from them.

APA, Harvard, Vancouver, ISO, and other styles

17

McCROAN, KEITH D., and R. C. LACHER. "REGION COLORING, EDGE COLORING, AND SCAN-CONVERSION OF MAPS." International Journal of Computational Geometry & Applications 04, no. 04 (December 1994): 423–55. http://dx.doi.org/10.1142/s0218195994000239.

Full text

Abstract:

A theory is introduced relating extrinsic colorings of complementary regions of an embedded graph to certain intrinsic colorings of the edges of the graph, called color cycles, that satisfy a certain self-consistency condition. A region coloring is lifted to an edge coloring satisfying the cycle condition, and a dual construction builds a region coloring from any color cycle and any embedding of the graph. Both constructs are canonical, and the constructions are information-conservative in the sense that lifting an arbitrary region coloring to a color cycle and then reconstructing a region coloring from the cycle, using the same embedding, results in the original region coloring. The theory is motivated by, and provides the proof of correctness of, new scan-conversion algorithms that are useful in settings where region boundaries have very high complexity. These algorithms have been implemented and provide useful display functionality previously unavailable on certain rastor devices.

APA, Harvard, Vancouver, ISO, and other styles

18

GESCHKE, STEFAN, MARTIN GOLDSTERN, and MENACHEM KOJMAN. "CONTINUOUS RAMSEY THEORY ON POLISH SPACES AND COVERING THE PLANE BY FUNCTIONS." Journal of Mathematical Logic 04, no. 02 (December 2004): 109–45. http://dx.doi.org/10.1142/s0219061304000334.

Full text

Abstract:

We investigate the Ramsey theory of continuous graph-structures on complete, separable metric spaces and apply the results to the problem of covering a plane by functions. Let the homogeneity number[Formula: see text] of a pair-coloring c:[X]2→2 be the number of c-homogeneous subsets of X needed to cover X. We isolate two continuous pair-colorings on the Cantor space 2ω, c min and c max , which satisfy [Formula: see text] and prove: Theorem. (1) For every Polish space X and every continuous pair-coloringc:[X]2→2with[Formula: see text], [Formula: see text] (2) There is a model of set theory in which[Formula: see text]and[Formula: see text]. The consistency of [Formula: see text] and of [Formula: see text] follows from [20]. We prove that [Formula: see text] is equal to the covering number of (2ω)2 by graphs of Lipschitz functions and their reflections on the diagonal. An iteration of an optimal forcing notion associated to c min gives: Theorem. There is a model of set theory in which (1) ℝ2 is coverable byℵ1graphs and reflections of graphs of continuous real functions; (2) ℝ2 is not coverable byℵ1graphs and reflections of graphs of Lipschitz real functions. Figure 1.1 in the introduction summarizes the ZFC results in Part I of the paper. The independence results in Part II show that any two rows in Fig. 1.1 can be separated if one excludes [Formula: see text] from row (3).

APA, Harvard, Vancouver, ISO, and other styles

19

Durgun, Derya, and Busra Ozen-Dortok. "Packing chromatic number of transformation graphs." Thermal Science 23, Suppl. 6 (2019): 1991–95. http://dx.doi.org/10.2298/tsci190720363d.

Full text

Abstract:

Graph coloring is an assignment of labels called colors to elements of a graph. The packing coloring was introduced by Goddard et al. [1] in 2008 which is a kind of coloring of a graph. This problem is NP-complete for general graphs. In this paper, we consider some transformation graphs and generalized their packing chromatic numbers.

APA, Harvard, Vancouver, ISO, and other styles

20

Barát, János, and Péter Varjú. "On square-free vertex colorings of graphs." Studia Scientiarum Mathematicarum Hungarica 44, no. 3 (September 1, 2007): 411–22. http://dx.doi.org/10.1556/sscmath.2007.1029.

Full text

Abstract:

A sequence of symbols a1 , a2 … is called square-free if it does not contain a subsequence of consecutive terms of the form x1 , …, xm , x1 , …, xm . A century ago Thue showed that there exist arbitrarily long square-free sequences using only three symbols. Sequences can be thought of as colors on the vertices of a path. Following the paper of Alon, Grytczuk, Hałuszczak and Riordan, we examine graph colorings for which the color sequence is square-free on any path. The main result is that the vertices of any k -tree have a coloring of this kind using O ( ck ) colors if c > 6. Alon et al. conjectured that a fixed number of colors suffices for any planar graph. We support this conjecture by showing that this number is at most 12 for outerplanar graphs. On the other hand we prove that some outerplanar graphs require at least 7 colors. Using this latter we construct planar graphs, for which at least 10 colors are necessary.

APA, Harvard, Vancouver, ISO, and other styles

21

Mellor, Blake, Terry Kong, Alec Lewald, and Vadim Pigrish. "Colorings, determinants and Alexander polynomials for spatial graphs." Journal of Knot Theory and Its Ramifications 25, no. 04 (April 2016): 1650019. http://dx.doi.org/10.1142/s021821651650019x.

Full text

Abstract:

A balanced spatial graph has an integer weight on each edge, so that the directed sum of the weights at each vertex is zero. We describe the Alexander module and polynomial for balanced spatial graphs (originally due to S. Kinoshita, Alexander polynomials as isotopy invariants I, Osaka Math. J. 10 (1958) 263–271.), and examine their behavior under some common operations on the graph. We use the Alexander module to define the determinant and [Formula: see text]-colorings of a balanced spatial graph, and provide examples. We show that the determinant of a spatial graph determines for which [Formula: see text] the graph is [Formula: see text]-colorable, and that a [Formula: see text]-coloring of a graph corresponds to a representation of the fundamental group of its complement into a metacyclic group [Formula: see text]. We finish by proving some properties of the Alexander polynomial.

APA, Harvard, Vancouver, ISO, and other styles

22

Razvenskaya, Olga O. "On new algorithmic techniques for the weighted vertex coloring problem." Zhurnal Srednevolzhskogo Matematicheskogo Obshchestva 22, no. 4 (December 31, 2020): 442–48. http://dx.doi.org/10.15507/2079-6900.22.202004.442-448.

Full text

Abstract:

The classical NP-hard weighted vertex coloring problem consists in minimizing the number of colors in colorings of vertices of a given graph so that, for each vertex, the number of its colors equals a given weight of the vertex and adjacent vertices receive distinct colors. The weighted chromatic number is the smallest number of colors in these colorings. There are several polynomial-time algorithmic techniques for designing efficient algorithms for the weighted vertex coloring problem. For example, standard techniques of this kind are the modular graph decomposition and the graph decomposition by separating cliques. This article proposes new polynomial-time methods for graph reduction in the form of removing redundant vertices and recomputing weights of the remaining vertices so that the weighted chromatic number changes in a controlled manner. We also present a method of reducing the weighted vertex coloring problem to its unweighted version and its application. This paper contributes to the algorithmic graph theory.

APA, Harvard, Vancouver, ISO, and other styles

23

Naduvath, Sudev, and Johan Kok. "J-coloring of graph operations." Acta Universitatis Sapientiae, Informatica 11, no. 1 (August 1, 2019): 95–108. http://dx.doi.org/10.2478/ausi-2019-0007.

Full text

Abstract:

Abstract A vertex v of a given graph is said to be in a rainbow neighbourhood of G if every color class of G consists of at least one vertex from the closed neighbourhood N[v]. A maximal proper coloring of a graph G is a J-coloring if and only if every vertex of G belongs to a rainbow neighbourhood of G. In general all graphs need not have a J-coloring, even though they admit a chromatic coloring. In this paper, we characterise graphs which admit a J-coloring. We also discuss some preliminary results in respect of certain graph operations which admit a J-coloring under certain conditions.

APA, Harvard, Vancouver, ISO, and other styles

24

Nagarathinam, R., N. Parvathi, and . "Grundy Number of Some Chordal Graphs." International Journal of Engineering & Technology 7, no. 4.10 (October 2, 2018): 64. http://dx.doi.org/10.14419/ijet.v7i4.10.20708.

Full text

Abstract:

For a given graph G and integer k, the Coloring problem is that of testing whether G has a k-coloring, that is, whether there exists a vertex mapping c : V → {1, 2, . . .} such that c(u) 12â‰ "> c(v) for every edge uv ∈ E. For proper coloring, colors assigned must be minimum, but for Grundy coloring which should be maximum. In this instance, Grundy numbers of chordal graphs like Cartesian product of two path graphs, join of the path and complete graphs and the line graph of tadpole have been executed

APA, Harvard, Vancouver, ISO, and other styles

25

Repalle, V. N. Srinivasa Rao, and Fekadu Tesgera Agama. "2-Quasitotal Fuzzy Graphs and Their Total Coloring." Advances in Fuzzy Systems 2020 (November 20, 2020): 1–10. http://dx.doi.org/10.1155/2020/8814220.

Full text

Abstract:

Coloring of fuzzy graphs has many real-life applications in combinatorial optimization problems like traffic light system, exam scheduling, and register allocation. The coloring of total fuzzy graphs and its applications are well studied. This manuscript discusses the description of 2-quasitotal graph for fuzzy graphs. The proposed concept of 2-quasitotal fuzzy graph is explicated by several numerical examples. Moreover, some theorems related to the properties of 2-quasitotal fuzzy graphs are stated and proved. The results of these theorems are compared with the results obtained from total fuzzy graphs and 1-quasitotal fuzzy graphs. Furthermore, it defines 2-quasitotal coloring of fuzzy total graphs and which is justified.

APA, Harvard, Vancouver, ISO, and other styles

26

Wenni, Mariza. "BILANGAN KROMATIK LOKASI DARI GRAF P m P n ; K m P n ; DAN K , m K n." Jurnal Matematika UNAND 2, no. 1 (March 10, 2013): 14. http://dx.doi.org/10.25077/jmu.2.1.14-22.2013.

Full text

Abstract:

Let G and H be two connected graphs. Let c be a vertex k-coloring of aconnected graph G and let = fCg be a partition of V (G) into the resultingcolor classes. For each v 2 V (G), the color code of v is dened to be k-vector: c1; C2; :::; Ck(v) =(d(v; C1); d(v; C2); :::; d(v; Ck)), where d(v; Ci) = minfd(v; x) j x 2 Cg, 1 i k. Ifdistinct vertices have distinct color codes with respect to , then c is called a locatingcoloring of G. The locating chromatic number of G is the smallest natural number ksuch that there are locating coloring with k colors in G. The Cartesian product of graphG and H is a graph with vertex set V (G) V (H), where two vertices (a; b) and (a)are adjacent whenever a = a0and bb02 E(H), or aa0i2 E(G) and b = b, denotedby GH. In this paper, we will study about the locating chromatic numbers of thecartesian product of two paths, the cartesian product of paths and complete graphs, andthe cartesian product of two complete graphs.

APA, Harvard, Vancouver, ISO, and other styles

27

D'Souza, S., K. P. Girija, and H. J. Gowtham. "Цветовая энергия некоторых кластерных графов." Владикавказский математический журнал, no. 2 (June 24, 2021): 51–64. http://dx.doi.org/10.46698/x5522-9720-4842-z.

Full text

Abstract:

Let $G$ be a simple connected graph. The energy of a graph $G$ is defined as sum of the absolute eigenvalues of an adjacency matrix of the graph $G$. It represents a proper generalization of a formula valid for the total $\pi$-electron energy of a conjugated hydrocarbon as calculated by the Huckel molecular orbital (HMO) method in quantum chemistry. A coloring of a graph $G$ is a coloring of its vertices such that no two adjacent vertices share the same color. The minimum number of colors needed for the coloring of a graph $G$ is called the chromatic number of $G$ and is denoted by $\chi(G)$. The color energy of a graph $G$ is defined as the sum of absolute values of the color eigenvalues of $G$. The graphs with large number of edges are referred as cluster graphs. Cluster graphs are graphs obtained from complete graphs by deleting few edges according to some criteria. It can be obtained on deleting some edges incident on a vertex, deletion of independent edges/triangles/cliques/path P3 etc. Bipartite cluster graphs are obtained by deleting few edges from complete bipartite graphs according to some rule. In this paper, the color energy of cluster graphs and bipartite cluster graphs are studied.

APA, Harvard, Vancouver, ISO, and other styles

28

Dong, Gui Xiang, and Xiu Fang Liu. "Incidence Coloring Number of Some Join Graphs." Applied Mechanics and Materials 602-605 (August 2014): 3185–88. http://dx.doi.org/10.4028/www.scientific.net/amm.602-605.3185.

Full text

Abstract:

The incidence coloring of a graph is a mapping from its incidence set to color set in which neighborly incidences are assigned different colors. In this paper, we determined the incidence coloring numbers of some join graphs with paths and paths, cycles, complete graphs, complete bipartite graphs, respectively, and the incidence coloring numbers of some join graphs with complete bipartite graphs and cycles, complete graphs, respectively.

APA, Harvard, Vancouver, ISO, and other styles

29

Malairaj, Rajeswari, and Sahul Hamid Isnail. "On global dominating -X-coloring of graphs." Tamkang Journal of Mathematics 48, no. 2 (June 30, 2017): 149–57. http://dx.doi.org/10.5556/j.tkjm.48.2017.2295.

Full text

Abstract:

Let $G$ be a graph. Among all $\chi$-colorings of $G$, a coloring with the maximum number of color classes that are global dominating sets in $G$ is called a global dominating-$\chi$-coloring of $G$. The number of color classes that are global dominating sets in a global dominating-$\chi$-coloring of $G$ is defined to be the global dominating -$\chi$- color number of $G$, denoted by $gd_{\chi}(G)$. This concept was introduced in \cite{a78}. This paper extends the study of this notion.

APA, Harvard, Vancouver, ISO, and other styles

30

Formanowicz, Piotr, and Krzysztof Tanaś. "A survey of graph coloring - its types, methods and applications." Foundations of Computing and Decision Sciences 37, no. 3 (October 1, 2012): 223–38. http://dx.doi.org/10.2478/v10209-011-0012-y.

Full text

Abstract:

Abstract Graph coloring is one of the best known, popular and extensively researched subject in the field of graph theory, having many applications and conjectures, which are still open and studied by various mathematicians and computer scientists along the world. In this paper we present a survey of graph coloring as an important subfield of graph theory, describing various methods of the coloring, and a list of problems and conjectures associated with them. Lastly, we turn our attention to cubic graphs, a class of graphs, which has been found to be very interesting to study and color. A brief review of graph coloring methods (in Polish) was given by Kubale in [32] and a more detailed one in a book by the same author. We extend this review and explore the field of graph coloring further, describing various results obtained by other authors and show some interesting applications of this field of graph theory.

APA, Harvard, Vancouver, ISO, and other styles

31

GANDHI, RAJIV, BRADFORD GREENING, SRIRAM PEMMARAJU, and RAJIV RAMAN. "SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS." Discrete Mathematics, Algorithms and Applications 02, no. 03 (September 2010): 331–45. http://dx.doi.org/10.1142/s1793830910000693.

Full text

Abstract:

In this paper, we study the sub-coloring and hypo-coloring problems on interval graphs. These problems have applications in job scheduling and distributed computing and can be used as "subroutines" for other combinatorial optimization problems. In the sub-coloring problem, given a graph G, we want to partition the vertices of G into minimum number of sub-color classes, where each sub-color class induces a union of disjoint cliques in G. In the hypo-coloring problem, given a graph G, and integral weights on vertices, we want to find a partition of the vertices of G into sub-color classes such that the sum of the weights of the heaviest cliques in each sub-color class is minimized. We present a "forbidden subgraph" characterization of graphs with sub-chromatic number k and use this to derive a 3-approximation algorithm for sub-coloring interval graphs. For the hypo-coloring problem on interval graphs, we first show that it is NP-complete, and then via reduction to the max-coloring problem, show how to obtain an O( log n)-approximation algorithm for it.

APA, Harvard, Vancouver, ISO, and other styles

32

Shakila, M., and N. Rajakumari. "A Study on Radio Labeling of Diameter N-2 and Caterpillar Graphs." International Journal of Emerging Research in Management and Technology 6, no. 8 (June 25, 2018): 30. http://dx.doi.org/10.23956/ijermt.v6i8.115.

Full text

Abstract:

Radio labeling of graphs is a specific type of graph labeling. The basic type of graph labeling is vertex coloring; this is where the vertices of a graph G are assigned different colors so that adjacent vertices are not given the same color. A k-coloring of a graph G is a coloring that uses k colors. The chromatic number of a graph G is the minimum value for k such that a k-coloring exists for G [2].

APA, Harvard, Vancouver, ISO, and other styles

33

Liu, Jia-Bao, Micheal Arockiaraj, and Antony Nelson. "Tight Bounds on 1-Harmonious Coloring of Certain Graphs." Symmetry 11, no. 7 (July 15, 2019): 917. http://dx.doi.org/10.3390/sym11070917.

Full text

Abstract:

Graph coloring is one of the most studied problems in graph theory due to its important applications in task scheduling and pattern recognition. The main aim of the problem is to assign colors to the elements of a graph such as vertices and/or edges subject to certain constraints. The 1-harmonious coloring is a kind of vertex coloring such that the color pairs of end vertices of every edge are different only for adjacent edges and the optimal constraint that the least number of colors is to be used. In this paper, we investigate the graphs in which we attain the sharp bound on 1-harmonious coloring. Our investigation consists of a collection of basic graphs like a complete graph, wheel, star, tree, fan, and interconnection networks such as a mesh-derived network, generalized honeycomb network, complete multipartite graph, butterfly, and Benes networks. We also give a systematic and elegant way of coloring for these structures.

APA, Harvard, Vancouver, ISO, and other styles

34

Madaus, Alexander, Maisie Newman, and Heather M. Russell. "Dehn coloring and the dimer model for knots." Journal of Knot Theory and Its Ramifications 26, no. 03 (March 2017): 1741008. http://dx.doi.org/10.1142/s0218216517410085.

Full text

Abstract:

Fox coloring provides a combinatorial framework for studying dihedral representations of the knot group. The less well-known concept of Dehn coloring captures the same data. Recent work of Carter–Silver–Williams clarifies the relationship between the two focusing on how one transitions between Fox and Dehn colorings. In our work, we relate Dehn coloring to the dimer model for knots showing that Dehn coloring data is encoded by a certain weighted balanced overlaid Tait (BOT) graph. Using Kasteleyn theory, we provide graph theoretic methods for determining the structure of a knot’s coloring module. These constructions are closely related to Kauffman’s work on a state sum for the Alexander polynomial.

APA, Harvard, Vancouver, ISO, and other styles

35

Sahul Hamid, I., and M. Rajeswari. "Global dominating sets in minimum coloring." Discrete Mathematics, Algorithms and Applications 06, no. 03 (June 16, 2014): 1450044. http://dx.doi.org/10.1142/s179383091450044x.

Full text

Abstract:

In this paper, we introduce the concept of global dominating-χ-coloring of a graph and the corresponding parameter namely global dominating-χ-color number. Let G be a graph. Among all χ-colorings of G, a coloring with the maximum number of color classes that are global dominating sets in G is called a global dominating-χ-coloring of G. The number of color classes that are global dominating sets in a global dominating-χ-coloring of G is defined to be the global dominating-χ-color number of G, denoted by gd χ(G).

APA, Harvard, Vancouver, ISO, and other styles

36

SKULRATTANAKULCHAI, SAN, and HAROLD N. GABOW. "COLORING ALGORITHMS ON SUBCUBIC GRAPHS." International Journal of Foundations of Computer Science 15, no. 01 (February 2004): 21–40. http://dx.doi.org/10.1142/s0129054104002285.

Full text

Abstract:

We present efficient algorithms for three coloring problems on subcubic graphs. (A subcubic graph has maximum degree at most three.) The first algorithm is for 4-edge coloring, or more generally, 4-list-edge coloring. Our algorithm runs in linear time, and appears to be simpler than previous ones. The second algorithm is the first randomized EREW PRAM algorithm for the same problem. It uses O(n/ log n) processors and runs in O( log n) time with high probability, where n is the number of vertices of the graph. The third algorithm is the first linear-time algorithm to 5-total-color subcubic graphs. The fourth algorithm generalizes this to get the first linear-time algorithm to 5-list-total-color subcubic graphs. Our sequential algorithms are based on a method of ordering the vertices and edges by traversing a spanning tree of a graph in a bottom-up fashion. Our parallel algorithm is based on a simple decomposition principle for subcubic graphs.

APA, Harvard, Vancouver, ISO, and other styles

37

Kaliraj, K., V. Kowsalya, and Vernold Vivin. "On star coloring of Mycielskians." Indonesian Journal of Combinatorics 2, no. 2 (December 21, 2018): 82. http://dx.doi.org/10.19184/ijc.2018.2.2.3.

Full text

Abstract:

<p>In a search for triangle-free graphs with arbitrarily large chromatic numbers, Mycielski developed a graph transformation that transforms a graph <span class="math"><em>G</em></span> into a new graph <span class="math"><em>μ</em>(<em>G</em>)</span>, we now call the Mycielskian of <span class="math"><em>G</em></span>, which has the same clique number as <span class="math"><em>G</em></span> and whose chromatic number equals <span class="math"><em>χ</em>(<em>G</em>) + 1</span>. In this paper, we find the star chromatic number for the Mycielskian graph of complete graphs, paths, cycles and complete bipartite graphs.</p>

APA, Harvard, Vancouver, ISO, and other styles

38

Bouzenada, Mourad, Meriem Bensouyad, Nousseiba Guidoum, Ahmed Reghioua, and Djamel-eddine Saïdouni. "A Generalized Graph Strict Strong Coloring Algorithm." International Journal of Applied Metaheuristic Computing 3, no. 1 (January 2012): 24–33. http://dx.doi.org/10.4018/jamc.2012010103.

Full text

Abstract:

This paper examines the graph coloring problem. A graph strict strong coloring algorithm has been proposed for trees in Haddad and Kheddouci (2009). In this paper, the authors propose a new heuristic based algorithm for general graphs named GGSSCA (for Generalized Graph Strict Strong Coloring Algorithm). The authors show that the complexity of this algorithm is polynomial with considering the number of vertices.

APA, Harvard, Vancouver, ISO, and other styles

39

Sudev, N. K., K. P. Chithra, K. A. Germina, S. Satheesh, and Johan Kok. "On certain coloring parameters of Mycielski graphs of some graphs." Discrete Mathematics, Algorithms and Applications 10, no. 03 (June 2018): 1850030. http://dx.doi.org/10.1142/s1793830918500301.

Full text

Abstract:

Coloring the vertices of a graph [Formula: see text] according to certain conditions can be considered as a random experiment and a discrete random variable [Formula: see text] can be defined as the number of vertices having a particular color in the proper coloring of [Formula: see text]. The concepts of mean and variance, two important statistical measures, have also been introduced to the theory of graph coloring and determined the values of these parameters for a number of standard graphs. In this paper, we discuss the coloring parameters of the Mycielskian of certain standard graphs.

APA, Harvard, Vancouver, ISO, and other styles

40

Saenpholphat, Varaporn, and Ping Zhang. "Conditional resolvability in graphs: a survey." International Journal of Mathematics and Mathematical Sciences 2004, no. 38 (2004): 1997–2017. http://dx.doi.org/10.1155/s0161171204311403.

Full text

Abstract:

For an ordered setW={w1,w2,…,wk}of vertices and a vertexvin a connected graphG, the code ofvwith respect toWis thek-vectorcW(v)=(d(v,w1),d(v,w2),…,d(v,wk)), whered(x,y)represents the distance between the verticesxandy. The setWis a resolving set forGif distinct vertices ofGhave distinct codes with respect toW. The minimum cardinality of a resolving set forGis its dimensiondim(G). Many resolving parameters are formed by extending resolving sets to different subjects in graph theory, such as the partition of the vertex set, decomposition and coloring in graphs, or by combining resolving property with another graph-theoretic property such as being connected, independent, or acyclic. In this paper, we survey results and open questions on the resolving parameters defined by imposing an additional constraint on resolving sets, resolving partitions, or resolving decompositions in graphs.

APA, Harvard, Vancouver, ISO, and other styles

41

LISNA, P. C., and M. S. SUNITHA. "A Note on the b-Chromatic Number of Corona of Graphs." Journal of Interconnection Networks 15, no. 01n02 (March 2015): 1550004. http://dx.doi.org/10.1142/s0219265915500048.

Full text

Abstract:

A b-coloring of a graph G is a proper coloring of the vertices of G such that there exists a vertex in each color class joined to at least one vertex in each other color classes. The b-chromatic number of a graph G, denoted by [Formula: see text], is the maximal integer k such that G has a b-coloring with k colors. In this paper, the b-chromatic numbers of the coronas of cycles, star graphs and wheel graphs with different numbers of vertices, respectively, are obtained. Also the bounds for the b-chromatic number of corona of any two graphs is discussed.

APA, Harvard, Vancouver, ISO, and other styles

42

HUC, FLORIAN. "WEIGHTED-EDGE-COLORING OF k-DEGENERATE GRAPHS AND BIN-PACKING." Journal of Interconnection Networks 12, no. 01n02 (March 2011): 109–24. http://dx.doi.org/10.1142/s0219265911002861.

Full text

Abstract:

The weighted-edge-coloring problem of an edge-weighted graph whose weights are between 0 and 1, consists in finding a coloring using as few colors as possible and satisfying the following constraints: the sum of weights of edges with the same color and incident to the same vertex must be at most 1. In 1991, Chung and Ross conjectured that if G is bipartite, then [Formula: see text] colors are always sufficient to weighted-edge-color (G,w), where [Formula: see text] is the maximum of the sums of the weights of the edges incident to a vertex. We prove this is true for edge-weighted graphs with multiple edges whose underlying graph is a tree. We further generalise this conjecture to non-bipartite graphs and prove the generalised conjecture for simple edge-weighted outerplanar graphs. Finally, we introduce a list version of this coloring together with the list-bin-packing problem, which allows us to obtain new results concerning the original coloring for a specific class of graphs, namely the k-weight-degenerate weighted graph.

APA, Harvard, Vancouver, ISO, and other styles

43

Chartrand, Gary, David Erwin, and Ping Zhang. "Radio antipodal colorings of graphs." Mathematica Bohemica 127, no. 1 (2002): 57–69. http://dx.doi.org/10.21136/mb.2002.133978.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Escuadro, Henry, and Ping Zhang. "On detectable colorings of graphs." Mathematica Bohemica 130, no. 4 (2005): 427–45. http://dx.doi.org/10.21136/mb.2005.134214.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Gera, Ralucca, Futaba Okamoto, Craig Rasmussen, and Ping Zhang. "Set colorings in perfect graphs." Mathematica Bohemica 136, no. 1 (2011): 61–68. http://dx.doi.org/10.21136/mb.2011.141450.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Benevides, Fabrício S., Carlos Hoppen, and Rudini M. Sampaio. "Edge-colorings of graphs avoiding complete graphs with a prescribed coloring." Discrete Mathematics 340, no. 9 (September 2017): 2143–60. http://dx.doi.org/10.1016/j.disc.2017.04.011.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Mohan, S., and K. Somasundaram. "Total coloring of the prismatic graphs." Discrete Mathematics, Algorithms and Applications 12, no. 03 (March 17, 2020): 2050032. http://dx.doi.org/10.1142/s1793830920500329.

Full text

Abstract:

A total coloring of a graph is an assignment of colors to all the elements of the graph such that no two adjacent or incident elements receive the same color. A graph [Formula: see text] is prismatic, if for every triangle [Formula: see text], every vertex not in [Formula: see text] has exactly one neighbor in [Formula: see text]. In this paper, we prove the total coloring conjecture (TCC) for prismatic graphs and the tight bound of the TCC for some classes of prismatic graphs.

APA, Harvard, Vancouver, ISO, and other styles

48

K.S, Kanzul Fathima, and Jahir Hussain R. "An Introduction to Fuzzy Edge Coloring." JOURNAL OF ADVANCES IN MATHEMATICS 11, no. 10 (January 28, 2016): 5742–48. http://dx.doi.org/10.24297/jam.v11i10.801.

Full text

Abstract:

In this paper, a new concept of fuzzy edge coloring is introduced. The fuzzy edge coloring is an assignment of colors to edges of a fuzzy graph G. It is proper if no two strong adjacent edges of G will receive the same color. Fuzzy edge chromatic number of G is least positive integer for which G has a proper fuzzy edge coloring. In this paper, the fuzzy edge chromatic number of different classes of fuzzy graphs and the fuzzy edge chromatic number of fuzzy line graphs are found. Isochromatic fuzzy graph is also defined.

APA, Harvard, Vancouver, ISO, and other styles

49

ROSE, SMITHA, and SUDEV NADUVATH. "On equitable chromatic topological indices of some Mycielski graphs." Creative Mathematics and Informatics 29, no. 2 (September 30, 2021): 221–29. http://dx.doi.org/10.37193/cmi.2020.02.13.

Full text

Abstract:

In recent years, the notion of chromatic Zagreb indices has been introduced and studied for certain basic graph classes, as a coloring parallel of different Zagreb indices. A proper coloring C of a graph G, which assigns colors to the vertices of G such that the numbers of vertices in any two color classes differ by at most one, is called an equitable coloring of G. In this paper, we introduce the equitable chromatic Zagreb indices and equitable chromatic irregularity indices of some special classes of graphs called Mycielski graphs of paths and cycles.

APA, Harvard, Vancouver, ISO, and other styles

50

V, Lavinya, Vijayalakshmi D, and Priyanka S. "ON STAR COLOURING OF M(TM,N),M(TN),M(LN) AND M(SN)." Kongunadu Research Journal 5, no. 2 (December 30, 2018): 7–10. http://dx.doi.org/10.26524/krj262.

Full text

Abstract:

A Star coloring of an undirected graph G is a proper vertex coloring of G in which every path on four vertices contains at least three distinct colors. The Star chromatic number of an undirected graph Χs(G), denoted by(G) is the smallest integer k for which G admits a star coloring with k colors. In this paper, we obtain the exact value of the Star chromatic number of Middle graph of Tadpole graph, Snake graph, Ladder graph and Sunlet graphs denoted by M(Tm,n), M(Tn),M(Ln) and M(Sn) respectively.

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!