To see the other types of publications on this topic, follow the link: Graph coloring.
Journal articles on the topic 'Graph coloring'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 journal articles for your research on the topic 'Graph coloring.'
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
Prajnanaswaroopa, Shantharam, Jayabalan Geetha, Kanagasabapathi Somasundaram, and Teerapong Suksumran. "Total Coloring of Some Classes of Cayley Graphs on Non-Abelian Groups." Symmetry 14, no. 10 (October 17, 2022): 2173. http://dx.doi.org/10.3390/sym14102173.
Full textAbstract:
Total Coloring of a graph G is a type of graph coloring in which any two adjacent vertices, an edge, and its incident vertices or any two adjacent edges do not receive the same color. The minimum number of colors required for the total coloring of a graph is called the total chromatic number of the graph, denoted by χ″(G). Mehdi Behzad and Vadim Vizing simultaneously worked on the total colorings and proposed the Total Coloring Conjecture (TCC). The conjecture states that the maximum number of colors required in a total coloring is Δ(G)+2, where Δ(G) is the maximum degree of the graph G. Graphs derived from the symmetric groups are robust graph structures used in interconnection networks and distributed computing. The TCC is still open for the circulant graphs. In this paper, we derive the upper bounds for χ″(G) of some classes of Cayley graphs on non-abelian groups, typically Cayley graphs on the symmetric groups and dihedral groups. We also obtain the upper bounds of the total chromatic number of complements of Kneser graphs.
2
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 textAbstract:
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.
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 textAbstract:
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.
4
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 textAbstract:
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.
5
Nuroeni, Ilmiatun, Arika Indah Kristiana, Saddam Hussen, Susi Setiawani, and Robiatul Adawiyah. "LOCAL IRREGULARITY POINT COLORING ON THE RESULT OF SUBDIVISION OPERATION OF HELM GRAPHS." Jurnal Diferensial 5, no. 2 (October 20, 2023): 117–25. http://dx.doi.org/10.35508/jd.v5i2.12197.
Full textAbstract:
One of the sub-chapters studied in graphs is local irregularity vertex coloring of graph. The based on definition of local irregularity vertex coloring of graph, as follow : (i)l : V (G) →{1, 2, 3, . . . , k} as a vertex irregular labeling and w : V (G) → N, for every uv ∈ E(G), w(u) ̸=w(v) with w(u) = Pv∈N(u)l(v) and (i) Opt(l) = min{max(li); li is a vertex irregular labeling}. The chromatic number of the local irregularity vertex coloring of G denoted by χlis(G), is the minimum cardinality of the largest label over all such local irregularity vertex colorings. In this article, discuss about local irregularity vertex coloring of subdivision by helm graph (Sg(Hn)).
6
Ma, Baolin, and Chao Yang. "Distinguishing colorings of graphs and their subgraphs." AIMS Mathematics 8, no. 11 (2023): 26561–73. http://dx.doi.org/10.3934/math.20231357.
Full textAbstract:
<abstract><p>In this paper, several distinguishing colorings of graphs are studied, such as vertex distinguishing proper edge coloring, adjacent vertex distinguishing proper edge coloring, vertex distinguishing proper total coloring, adjacent vertex distinguishing proper total coloring. Finally, some related chromatic numbers are determined, especially the comparison of the correlation chromatic numbers between the original graph and the subgraphs are obtained.</p></abstract>
7
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 textAbstract:
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.
8
Li, Minhui, Shumin Zhang, Caiyun Wang, and Chengfu Ye. "The Dominator Edge Coloring of Graphs." Mathematical Problems in Engineering 2021 (October 7, 2021): 1–7. http://dx.doi.org/10.1155/2021/8178992.
Full textAbstract:
Let G be a simple graph. A dominator edge coloring (DE-coloring) of G is a proper edge coloring in which each edge of G is adjacent to every edge of some color class (possibly its own class). The dominator edge chromatic number (DEC-number) of G is the minimum number of color classes among all dominator edge colorings of G , denoted by χ d ′ G . In this paper, we establish the bounds of the DEC-number of a graph, present the DEC-number of special graphs, and study the relationship of the DEC-number between G and the operations of G .
9
A. Prasanna, M. A. Rifayathali, and S. Ismail Mohideen. "Hesitancy Fuzzy Graph Coloring." International Journal of Fuzzy Mathematical Archive 14, no. 02 (2017): 179–89. http://dx.doi.org/10.22457/ijfma.v14n2a2.
Full textAbstract:
Graph coloring dates back to 1852, when Francis Guthrie come up with the four color conjecture. Gary Chartrand and Ping Zhang [3] discussed various colorings of graph and its properties in their book entitled Chromatic Graph Theory. A graph coloring is the assignment of a color to each of the vertices or edges or both in such a way that no two adjacent vertices and incident edges share the same color. Graph coloring has been applied to many real world problems like scheduling, allocation, telecommunications and bioinformatics, etc.
10
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 textAbstract:
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.
11
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 textAbstract:
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.
12
Khachatryan, H. H. "DEFICIENCY OF OUTERPLANAR GRAPHS." Proceedings of the YSU A: Physical and Mathematical Sciences 51, no. 1 (242) (March 20, 2017): 22–28. http://dx.doi.org/10.46991/pysu:a/2017.51.1.022.
Full textAbstract:
An edge-coloring of a graph G with colors $1,2,...,t$ is an interval $t$-coloring, if all colors are used, and the colors of edges incident to each vertex of $G$ are distinct and form an interval of integers. A graph $G$ is interval colorable, if it has an interval $t$-coloring for some positive integer $t$. $def (G)$ denotes the minimum number of pendant edges that should be attached to $G$ to make it interval colorable. In this paper we study interval colorings of outerplanar graphs. In particular, we show that if $G$ is an outerplanar graph, then $def(G) \leq (|V(G)|-2)/(og(G)-2)$, where $og(G)$ is the length of the shortest cycle with odd number of edges in $G$.
13
Dai, Zemiao, Muhammad Naeem, Zainab Shafaqat, Manzoor Ahmad Zahid, and Shahid Qaisar. "On the P3-Coloring of Bipartite Graphs." Mathematics 11, no. 16 (August 12, 2023): 3487. http://dx.doi.org/10.3390/math11163487.
Full textAbstract:
The advancement in coloring schemes of graphs is expanding over time to solve emerging problems. Recently, a new form of coloring, namely P3-coloring, was introduced. A simple graph is called a P3-colorable graph if its vertices can be colored so that all the vertices in each P3 path of the graph have different colors; this is called the P3-coloring of the graph. The minimum number of colors required to form a P3-coloring of a graph is called the P3-chromatic number of the graph. The aim of this article is to determine the P3-chromatic number of different well-known classes of bipartite graphs such as complete bipartite graphs, tree graphs, grid graphs, and some special types of bipartite graphs. Moreover, we have also presented some algorithms to produce a P3-coloring of these classes with a minimum number of colors required.
14
Kristiana, Arika Indah, M. Hidayat, Robiatul Adawiyah, D. Dafik, Susi Setiawani, and Ridho Alfarisi. "ON LOCAL IRREGULARITY OF THE VERTEX COLORING OF THE CORONA PRODUCT OF A TREE GRAPH." Ural Mathematical Journal 8, no. 2 (December 29, 2022): 94. http://dx.doi.org/10.15826/umj.2022.2.008.
Full textAbstract:
Let \(G=(V,E)\) be a graph with a vertex set \(V\) and an edge set \(E\). The graph \(G\) is said to be with a local irregular vertex coloring if there is a function \(f\) called a local irregularity vertex coloring with the properties: (i) \(l:(V(G)) \to \{ 1,2,...,k \} \) as a vertex irregular \(k\)-labeling and \(w:V(G)\to N,\) for every \(uv \in E(G),\) \({w(u)\neq w(v)}\) where \(w(u)=\sum_{v\in N(u)}l(i)\) and (ii) \(\mathrm{opt}(l)=\min\{ \max \{ l_{i}: l_{i} \ \text{is a vertex irregular labeling}\}\}\). The chromatic number of the local irregularity vertex coloring of \(G\) denoted by \(\chi_{lis}(G)\), is the minimum cardinality of the largest label over all such local irregularity vertex colorings. In this paper, we study a local irregular vertex coloring of \(P_m\bigodot G\) when \(G\) is a family of tree graphs, centipede \(C_n\), double star graph \((S_{2,n})\), Weed graph \((S_{3,n})\), and \(E\) graph \((E_{3,n})\).
15
Labbate, Domenico, Davide Mattiolo, Giuseppe Mazzuoccolo, Federico Romaniello, and Gloria Tabarelli. "A Characterization of Graphs with Small Palette Index." Symmetry 15, no. 1 (January 4, 2023): 154. http://dx.doi.org/10.3390/sym15010154.
Full textAbstract:
Given an edge-coloring of a graph G, we associate to every vertex v of G the set of colors appearing on the edges incident with v. The palette index of G is defined as the minimum number of such distinct sets, taken over all possible edge-colorings of G. A graph with a small palette index admits an edge-coloring which can be locally considered to be almost symmetric, since few different sets of colors appear around its vertices. Graphs with palette index 1 are r-regular graphs admitting an r-edge-coloring, while regular graphs with palette index 2 do not exist. Here, we characterize all graphs with palette index either 2 or 3 in terms of the existence of suitable decompositions in regular subgraphs. As a corollary, we obtain a complete characterization of regular graphs with palette index 3.
16
Yang, Hong, Muhammad Naeem, and Shahid Qaisar. "On the P3 Coloring of Graphs." Symmetry 15, no. 2 (February 15, 2023): 521. http://dx.doi.org/10.3390/sym15020521.
Full textAbstract:
The vertex coloring of graphs is a well-known coloring of graphs. In this coloring, all of the vertices are assigned colors in such a way that no two adjacent vertices have the same color. We can call this type of coloring P2 coloring, where P2 is a path graph. However, there are situations in which this type of coloring cannot give us the solution to the problem at hand. To answer such questions, in this article, we introduce a novel graph coloring called P3 coloring. A graph is called P3-colorable if we can assign colors to the vertices of the graph such that the vertices of every P3 path are distinct. The minimum number of colors required for a graph to have P3 coloring is called the P3 chromatic number. The aim of this article is, in general, to prove some basic results concerning this coloring, and, in particular, to compute the P3 chromatic number for different symmetric families of graphs.
17
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 textAbstract:
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.
18
Zhou, Yangyang, Dongyang Zhao, Mingyuan Ma, and Jin Xu. "Domination Coloring of Graphs." Mathematics 10, no. 6 (March 21, 2022): 998. http://dx.doi.org/10.3390/math10060998.
Full textAbstract:
A domination coloring of a graph G is a proper vertex coloring of G, such that each vertex of G dominates at least one color class (possibly its own class), and each color class is dominated by at least one vertex. The minimum number of colors among all domination colorings is called the domination chromatic number, denoted by χdd(G). In this paper, we study the complexity of the k-domination coloring problem by proving its NP-completeness for arbitrary graphs. We give basic results and properties of χdd(G), including the bounds and characterization results, and further research χdd(G) of some special classes of graphs, such as the split graphs, the generalized Petersen graphs, corona products, and edge corona products. Several results on graphs with χdd(G)=χ(G) are presented. Moreover, an application of domination colorings in social networks is proposed.
19
Zhong, Chuang, and Shuangliang Tian. "Neighbor Sum Distinguishing Edge (Total) Coloring of Generalized Corona Product." Journal of Physics: Conference Series 2381, no. 1 (December 1, 2022): 012031. http://dx.doi.org/10.1088/1742-6596/2381/1/012031.
Full textAbstract:
Abstract The coloring theory of graphs is an important part of graph theory research. The key problem of the coloring theory of graphs is to determine the coloring number of each kind of coloring. Traditional coloring concepts mainly include proper vertex coloring, proper edge coloring, proper total coloring, and so on. In recent years, scholars at home and abroad have put forward some new coloring concepts, such as neighbor vertex distinguishing edge (total) coloring, and neighbor sum distinguishing edge (total) coloring, based on traditional coloring concepts and by adding other constraints. Some valuable results have been obtained, which further enrich the theory of graph coloring. For a proper [k]-edge coloring of a graph G, if for any adjacent vertex has a different sum of colors, then the coloring is a neighbor sum distinguishing [k]-edge coloring of G. For a proper [k]-total coloring of a graph G, if for any adjacent vertex has a different sum of colors, then the coloring is a neighbor sum distinguishing [k]-total coloring of G . In this paper, the coloring method and coloring index are determined by the process of induction and deduction and the construction of the dyeing method, and then the rationality of the method is verified by inverse proof and mathematical induction. If G is a simple graph with the order n ≥ 5 , and hn = (Hi ) i∈{1,2,…,n} is a sequence of disjoint simple graphs, where every Hi is a simple graph with the order m ≥ 7 . In this paper, we study the neighbor sum distinguishing edge(total) coloring of the generalized corona product G○hn of G and hn . The results are as follows: (1) If G is a path with order n , hn = (Hi ) i∈{1,2,…,n} is an alternating sequence of path and cycle with order m . If n is odd, we have χ Σ ′ ( G ∘ h n ) = m + 3 (2) If G is a path with order n , hn = (Hi ) i∈{1,2,…,n} is an alternating sequence of path and cycle with order m . If n is odd, we have χ Σ ′ ′ ( G ∘ h n ) = m + 4 Due to the late development of neighbor sum distinguishing edge (total) coloring of graphs, the related research results are relatively few. By studying the operation graph of a basic simple graph, we can provide the research basis and reference idea for the corresponding coloring of the general graph class. Therefore, it is of theoretical value to study the neighbor sum distinguishing edge (total) coloring problem of generalized corona products of graphs.
20
K.Kalaiarasi and L.Mahalakshmi. "Coloring of Regular and Strong Arcs Fuzzy Graphs." International Journal of Fuzzy Mathematical Archive 14, no. 01 (2017): 59–68. http://dx.doi.org/10.22457/ijfma.v14n1a8.
Full textAbstract:
In this paper, we introduce coloring of regular fuzzy graph G=(V,B). We can apply two different approaches to coloring of Regular fuzzy graph. The first approach is based on the odd regular coloring fuzzy graphs and the second approach is based on the even regular coloring fuzzy graph. We establish strong coloring of a fuzzy graph and we change δ − arc into α − arc or β − arc .
21
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 textAbstract:
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.
22
Chartrand, Gary, James Hallas, and Ping Zhang. "Royal Colorings of Graphs." Ars Combinatoria 156 (July 31, 2023): 51–63. http://dx.doi.org/10.61091/ars156-06.
Full textAbstract:
For a graph \(G\) and a positive integer \(k\), a royal \(k\)-edge coloring of \(G\) is an assignment of nonempty subsets of the set \(\{1, 2, \ldots, k\}\) to the edges of \(G\) that gives rise to a proper vertex coloring in which the color assigned to each vertex \(v\) is the union of the sets of colors of the edges incident with \(v\). If the resulting vertex coloring is vertex-distinguishing, then the edge coloring is a strong royal \(k\)-coloring. The minimum positive integer \(k\) for which a graph has a strong royal \(k\)-coloring is the strong royal index of the graph. The primary emphasis here is on strong royal colorings of trees.
23
Chartrand, Gary, James Hallas, and Ping Zhang. "Royal Colorings of Graphs." Ars Combinatoria 156 (July 31, 2023): 51–63. http://dx.doi.org/10.61091/ars156-6.
Full textAbstract:
For a graph G and a positive integer k , a royal k -edge coloring of G is an assignment of nonempty subsets of the set { 1 , 2 , … , k } to the edges of G that gives rise to a proper vertex coloring in which the color assigned to each vertex v is the union of the sets of colors of the edges incident with v . If the resulting vertex coloring is vertex-distinguishing, then the edge coloring is a strong royal k coloring. The minimum positive integer k for which a graph has a strong royal k -coloring is the strong royal index of the graph. The primary emphasis here is on strong royal colorings of trees.
24
Muradyan, Levon N. "ON INTERVAL EDGE-COLORINGS OF COMPLETE MULTIPARTITE GRAPHS." Proceedings of the YSU A: Physical and Mathematical Sciences 56, no. 1 (257) (March 25, 2022): 19–26. http://dx.doi.org/10.46991/pysu:a/2022.56.1.019.
Full textAbstract:
A graph $G$ is called a complete $r$-partite $(r\geq 2)$ graph, if its vertices can be divided into $r$ non-empty independent sets $V_1,\ldots,V_r$ in a way that each vertex in $V_i$ is adjacent to all the other vertices in $V_j$ for $1\leq i<j\leq r$. Let $K_{n_{1},n_{2},\ldots,n_{r}}$ denote a complete $r$-partite graph with independent sets $V_1,V_2,\ldots,V_r$ of sizes $n_{1},n_{2},\ldots,n_{r}$. An edge-coloring of a graph $G$ with colors $1,2,\ldots,t$ is called an \emph{interval $t$-coloring}, if all colors are used and the colors of edges incident to each vertex of $G$ are distinct and form an interval of integers. In this paper we have obtained some results on the existence and construction of interval edge-colorings of complete $r$-partite graphs. Moreover, we have also derived an upper bound on the number of colors in interval colorings of complete multipartite graphs.
25
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 textAbstract:
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.
26
Septory, Brian Juned, Liliek Susilowati, Dafik Dafik, and M. Venkatachalam. "On Rainbow Antimagic Coloring of Joint Product of Graphs." CAUCHY: Jurnal Matematika Murni dan Aplikasi 7, no. 4 (May 24, 2023): 548–58. http://dx.doi.org/10.18860/ca.v7i4.17471.
Full textAbstract:
Let be a connected graph with vertex set and edge set . A bijection from to the set is a labeling of graph . The bijection is called rainbow antimagic vertex labeling if for any two edge and in path , where and . Rainbow antimagic coloring is a graph which has a rainbow antimagic labeling. Thus, every rainbow antimagic labeling induces a rainbow coloring G where the edge weight is the color of the edge . The rainbow antimagic connection number of graph is the smallest number of colors of all rainbow antimagic colorings of graph , denoted by . In this study, we studied rainbow antimagic coloring and have an exact value of rainbow antimagic connection number of joint product of graph where is graph , graph , graph , graph and graph .
27
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 textAbstract:
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.
28
Wang, Yiqiao, Juan Liu, Yongtang Shi, and Weifan Wang. "Star Chromatic Index of 1-Planar Graphs." Symmetry 14, no. 6 (June 8, 2022): 1177. http://dx.doi.org/10.3390/sym14061177.
Full textAbstract:
Many symmetric properties are well-explored in graph theory, especially in graph coloring, such as symmetric graphs defined by the automorphism groups, symmetric drawing of planar graphs, and symmetric functions which are used to count the number of specific colorings of a graph. This paper is devoted to studying the star edge coloring of 1-planar graphs. The star chromatic index χst′(G) of a graph G is defined as the smallest k for which the edges of G can be colored by using k colors so that no two adjacent edges get the same color and no bichromatic paths or cycles of length four are produced. A graph G is called 1-planar if it can be drawn in the plane such that each edge crosses at most one other edge. In this paper, we prove that every 1-planar graph G satisfies χst′(G)≤7.75Δ+166; and moreover χst′(G)≤⌊1.5Δ⌋+500 if G contains no 4-cycles, and χst′(G)≤2.75Δ+116 if G is 3-connected, or optimal, or NIC-planar.
29
Brannan, Michael, Priyanga Ganesan, and Samuel J. Harris. "The quantum-to-classical graph homomorphism game." Journal of Mathematical Physics 63, no. 11 (November 1, 2022): 112204. http://dx.doi.org/10.1063/5.0072288.
Full textAbstract:
Motivated by non-local games and quantum coloring problems, we introduce a graph homomorphism game between quantum graphs and classical graphs. This game is naturally cast as a “quantum–classical game,” that is, a non-local game of two players involving quantum questions and classical answers. This game generalizes the graph homomorphism game between classical graphs. We show that winning strategies in the various quantum models for the game is an analog of the notion of non-commutative graph homomorphisms due to Stahlke [IEEE Trans. Inf. Theory 62(1), 554–577 (2016)]. Moreover, we present a game algebra in this context that generalizes the game algebra for graph homomorphisms given by Helton et al. [New York J. Math. 25, 328–361 (2019)]. We also demonstrate explicit quantum colorings of all quantum complete graphs, yielding the surprising fact that the algebra of the four coloring game for a quantum graph is always non-trivial, extending a result of Helton et al. [New York J. Math. 25, 328–361 (2019)].
30
Yusuf, Riduan, Fitria Puspa Dewi, Firmansyah Firmansyah, and Abdul Mujib. "Generalisasi Bilangan Kromatik Pada Beberapa Kelas Graf Korona." Jurnal Derivat: Jurnal Matematika dan Pendidikan Matematika 9, no. 2 (December 20, 2022): 192–201. http://dx.doi.org/10.31316/jderivat.v9i2.3780.
Full textAbstract:
For example is a chromatic number with the smallest integer so that the graph has a true vertex coloring with k color. Chromatic number is still an interesting study which is still being studied for its development through graph coloring. Graph coloring is a special case of graph labeling. Labeling here means, giving color to the points at a certain limit so that no two vertices have the same color. This study aims to calculate the chromatic number in several classes of graphs including , , Based on the results of the study, generalization of the chromatic number of the graph class . Class and for class for even n and 4 for odd n. Keywords: graph, graph coloring, chromatic number For example is a chromatic number with the smallest integer so that the graph has a true vertex coloring with k color. Chromatic number is still an interesting study which is still being studied for its development through graph coloring. Graph coloring is a special case of graph labeling. Labeling here means, giving color to the points at a certain limit so that no two vertices have the same color. This study aims to calculate the chromatic number in several classes of graphs including , , Based on the results of the study, generalization of the chromatic number of the graph class . Class and for class for even n and 4 for odd n. Keywords: graph, graph coloring, chromatic number
31
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 textAbstract:
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.
32
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 textAbstract:
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.
33
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 textAbstract:
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].
34
Sennaiyan, Balakrishnan, and Tamilarasi Suresh. "Graph Coloring on Bipartite Graphs." International Journal of Mathematical, Engineering, Biological and Applied Computing 1, no. 2 (September 11, 2022): 56–60. http://dx.doi.org/10.31586/ijmebac.2022.422.
Full text
35
Liang, Zuosong, and Huandi Wei. "A Linear-Time Algorithm for 4-Coloring Some Classes of Planar Graphs." Computational Intelligence and Neuroscience 2021 (October 5, 2021): 1–5. http://dx.doi.org/10.1155/2021/7667656.
Full textAbstract:
Every graph G = V , E considered in this paper consists of a finite set V of vertices and a finite set E of edges, together with an incidence function that associates each edge e ∈ E of G with an unordered pair of vertices of G which are called the ends of the edge e . A graph is said to be a planar graph if it can be drawn in the plane so that its edges intersect only at their ends. A proper k -vertex-coloring of a graph G = V , E is a mapping c : V ⟶ S ( S is a set of k colors) such that no two adjacent vertices are assigned the same colors. The famous Four Color Theorem states that a planar graph has a proper vertex-coloring with four colors. However, the current known proof for the Four Color Theorem is computer assisted. In addition, the correctness of the proof is still lengthy and complicated. In 2010, a simple O n 2 time algorithm was provided to 4-color a 3-colorable planar graph. In this paper, we give an improved linear-time algorithm to either output a proper 4-coloring of G or conclude that G is not 3-colorable when an arbitrary planar graph G is given. Using this algorithm, we can get the proper 4-colorings of 3-colorable planar graphs, planar graphs with maximum degree at most five, and claw-free planar graphs.
36
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 textAbstract:
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.
37
Mulati,, Mauro, Carla Lintzmayer, and Anderson Da Silva. "The Hybrid ColorAnt-RT Algorithms and an Application to Register Allocation." Inteligencia Artificial 18, no. 55 (May 18, 2015): 81. http://dx.doi.org/10.4114/intartif.vol18iss55pp81-111.
Full textAbstract:
Ant Colony Optimization is a metaheuristic used to create heuristic algorithms to find good solutions for combinatorial optimization problems. This metaheuristic is inspired on the effective behavior present in some species of ants of exploring the environment to find and transport food to the nest. Several works have proposed using Ant Colony Optimization algorithms to solve problems such as vehicle routing, frequency assignment, scheduling and graph coloring. The graph coloring problem essentially consists in finding a number k of colors to assign to the vertices of a graph, so that there are no two adjacent vertices with the same color. This paper presents the hybrid ColorAnt-RT algorithms, a class of algorithms for graph coloring problems which is based on the Ant Colony Optimization metaheuristic and uses Tabu Search as local search. The experiments with ColorAnt-RT algorithms indicate that changing the way to reinforce the pheromone trail results in better results. In fact, the results with ColorAnt-RT show that it is a promising option in finding good approximations of k. The good results obtained by ColorAnt-RT motivated it use on a register allocation based on Ant Colony Optimization, called CARTRA. As a result, this paper also presents CARTRA, an algorithm that extends a classic graph coloring register allocator to use the graph coloring algorithm ColorAnt-RT. CARTRA minimizes the amount of spills, thereby improving the quality of the generated code.
38
Huo, Jingjing, Sensen Wen, Yulong Chen, and Mingchao Li. "Neighbor Distinguishing Colorings of Graphs with the Restriction for Maximum Average Degree." Axioms 12, no. 12 (December 18, 2023): 1132. http://dx.doi.org/10.3390/axioms12121132.
Full textAbstract:
Neighbor distinguishing colorings of graphs represent powerful tools for solving the channel assignment problem in wireless communication networks. They consist of two forms of coloring: neighbor distinguishing edge coloring, and neighbor distinguishing total coloring. The neighbor distinguishing edge (total) coloring of a graph G is an edge (total) coloring with the requirement that each pair of adjacent vertices contains different color sets. The neighbor distinguishing edge (total) chromatic number of G is the smallest integer k in cases where a neighbor distinguishing edge (total) coloring exists through the use of k colors in G. The maximum average degree of G is the maximum of the average degree of its non-empty subgraphs. In this paper, we characterize the neighbor distinguishing edge (total) chromatic numbers of graphs with a maximum average degree less than four by means of the discharging method.
39
Tupper, Melissa, and Jacob A. White. "Online list coloring for signed graphs." Algebra and Discrete Mathematics 33, no. 2 (2022): 151–72. http://dx.doi.org/10.12958/adm1806.
Full textAbstract:
We generalize the notion of online list coloring to signed graphs. We define the online list chromatic number of a signed graph, and prove a generalization of Brooks' Theorem. We also give necessary and sufficient conditions for a signed graph to be degree paintable, or degree choosable. Finally, we classify the 2-list-colorable and 2-list-paintable signed graphs.
40
Noori, Noor Sabah, and Israa Monier Tawfiq. "Coloring Graph and Four-Color Theorem." Journal for Research in Applied Sciences and Biotechnology 2, no. 5 (October 28, 2023): 99–104. http://dx.doi.org/10.55544/jrasb.2.5.16.
Full textAbstract:
In this research, the topic of graph coloring was addressed, which includes coloring vertices, coloring edges, and coloring faces. Some relationships between the chromatic number and some graphs were also proven, and the color number of faces was obtained for some graphs, and a historical overview of one of the most important theorems in graph theory represented by the four-color theorem, was presented. The four-color theorem is applied to the map of Iraq and then transformed the map of Iraq into a graph.
41
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 textAbstract:
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].
42
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 textAbstract:
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.
43
Fran, Fransiskus, Nilamsari Kusumastuti, and Robiandi. "BILANGAN KROMATIK HARMONIS PADA GRAF PAYUNG, GRAF PARASUT, DAN GRAF SEMI PARASUT." Jurnal Matematika Sains dan Teknologi 24, no. 1 (May 20, 2023): 15–22. http://dx.doi.org/10.33830/jmst.v24i1.3945.2023.
Full textAbstract:
This article discusses the harmonic coloring of simple graphs G, namely umbrella graphs, parachute graphs, and semi-parachute graphs. A vertex coloring on a graph G is a harmonic coloring if each pair of colors (based on edges or pair of vertices) appears at most once. The chromatic number associated with the harmonic coloring of graph G is called the harmonic chromatic number denoted XH(G). In this article, the exact values of harmonic chromatic numbers are obtained for umbrella graphs, parachute graphs, and semi-parachute graphs.
44
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 textAbstract:
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.
45
Ghazaryan, Aghasi B., and Petros A. Petrosyan. "ON THE PALETTE INDEX OF GRAPHS HAVING A SPANNING STAR." Proceedings of the YSU A: Physical and Mathematical Sciences 56, no. 3 (259) (October 17, 2022): 85–96. http://dx.doi.org/10.46991/pysu:a/2022.56.3.085.
Full textAbstract:
A proper edge coloring of a graph $G$ is a mapping $\alpha:E(G)\longrightarrow \mathbb{N}$ such that $\alpha(e)\not=\alpha(e')$ for every pair of adjacent edges $e$ and $e'$ in $G$. In a proper edge coloring of a graph $G$, the palette of a vertex $v \in V(G)$ is the set of colors assigned to the edges incident to $v$. The palette index of $G$ is the minimum number of distinct palettes occurring in $G$ among all proper edge colorings of $G$. A graph $G$ has a spanning star, if it has a spanning subgraph which is a star. In this paper, we consider the palette index of graphs having a spanning star. In particular, we give sharp upper and lower bounds on the palette index of these graphs. We also provide some upper and lower bounds on the palette index of the complete split and threshold graphs.
46
Gong, Zengtai, and Chen Zhang. "Adjacent Vertex Distinguishing Coloring of Fuzzy Graphs." Mathematics 11, no. 10 (May 10, 2023): 2233. http://dx.doi.org/10.3390/math11102233.
Full textAbstract:
In this paper, we consider the adjacent vertex distinguishing proper edge coloring (for short, AVDPEC) and the adjacent vertex distinguishing total coloring (for short, AVDTC) of a fuzzy graph. Firstly, this paper describes the development process, the application areas, and the existing review research of fuzzy graphs and adjacent vertex distinguishing coloring of crisp graphs. Secondly, we briefly introduce the coloring theory of crisp graphs and the related theoretical basis of fuzzy graphs, and add some new classes of fuzzy graphs. Then, based on the α-cuts of fuzzy graphs and distance functions, we give two definitions of the AVDPEC of fuzzy graphs, respectively. A lower bound on the chromatic number of the AVDPEC of a fuzzy graph is obtained. With examples, we show that some results of the AVDPEC of a crisp graph do not carry over to our set up; the adjacent vertex distinguishing chromatic number of the fuzzy graph is different from the general chromatic number of a fuzzy graph. We also give a simple algorithm to construct a (d,f)-extended AVDPEC for fuzzy graphs. After that, in a similar way, two definitions of the AVDTC of fuzzy graphs are discussed. Finally, the future research directions of distinguishing coloring of fuzzy graphs are given.
47
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 textAbstract:
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.
48
Sedlar, Jelena, and Riste Škrekovski. "Remarks on the Local Irregularity Conjecture." Mathematics 9, no. 24 (December 12, 2021): 3209. http://dx.doi.org/10.3390/math9243209.
Full textAbstract:
A locally irregular graph is a graph in which the end vertices of every edge have distinct degrees. A locally irregular edge coloring of a graph G is any edge coloring of G such that each of the colors induces a locally irregular subgraph of G. A graph G is colorable if it allows a locally irregular edge coloring. The locally irregular chromatic index of a colorable graph G, denoted by χirr′(G), is the smallest number of colors used by a locally irregular edge coloring of G. The local irregularity conjecture claims that all graphs, except odd-length paths, odd-length cycles and a certain class of cacti are colorable by three colors. As the conjecture is valid for graphs with a large minimum degree and all non-colorable graphs are vertex disjoint cacti, we study rather sparse graphs. In this paper, we give a cactus graph B which contradicts this conjecture, i.e., χirr′(B)=4. Nevertheless, we show that the conjecture holds for unicyclic graphs and cacti with vertex disjoint cycles.
49
Sesa, Junianto, and Siswanto Siswanto. "Determination of Fractional Chromatic Numbers in the Operation of Adding Two Different Graphs." Jurnal Matematika, Statistika dan Komputasi 18, no. 2 (January 1, 2022): 161–68. http://dx.doi.org/10.20956/j.v18i2.14501.
Full textAbstract:
The development of graph theory has provided many new pieces of knowledge, one of them is graph color. Where the application is spread in various fields such as the coding index theory. Fractional coloring is multiple coloring at points with different colors where the adjoining point has a different color. The operation in the graph is known as the sum operation. Point coloring can be applied to graphs where the result of operations is from several special graphs. In this case, the graph summation results of the path graph and the cycle graph will produce the same fractional chromatic number as the sum of the fractional chromatic numbers of each graph before it is operated.
50
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 textAbstract:
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.