Log in

Relevant bibliographies by topics / Maximum Edge Coloring (Graphs) / Journal articles

To see the other types of publications on this topic, follow the link: Maximum Edge Coloring (Graphs).

Journal articles on the topic 'Maximum Edge Coloring (Graphs)'

Author: Grafiati

Published: 4 June 2021

Last updated: 6 September 2023

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 'Maximum Edge Coloring (Graphs).'

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 (2022): 2173. http://dx.doi.org/10.3390/sym14102173.

Full text

Abstract:

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. Graph

APA, Harvard, Vancouver, ISO, and other styles

2

HUC, FLORIAN. "WEIGHTED-EDGE-COLORING OF k-DEGENERATE GRAPHS AND BIN-PACKING." Journal of Interconnection Networks 12, no. 01n02 (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 m

APA, Harvard, Vancouver, ISO, and other styles

3

Obata, Yuji, and Takao Nishizeki. "Generalized edge-colorings of weighted graphs." Discrete Mathematics, Algorithms and Applications 08, no. 01 (2016): 1650015. http://dx.doi.org/10.1142/s1793830916500154.

Full text

Abstract:

Let [Formula: see text] be a graph with a positive integer weight [Formula: see text] for each vertex [Formula: see text]. One wishes to assign each edge [Formula: see text] of [Formula: see text] a positive integer [Formula: see text] as a color so that [Formula: see text] for any vertex [Formula: see text] and any two edges [Formula: see text] and [Formula: see text] incident to [Formula: see text]. Such an assignment [Formula: see text] is called an [Formula: see text]-edge-coloring of [Formula: see text], and the maximum integer assigned to edges is called the span of [Formula: see text].

APA, Harvard, Vancouver, ISO, and other styles

4

Jin, Zemin, Kun Ye, He Chen, and Yuefang Sun. "Large rainbow matchings in semi-strong edge-colorings of graphs." Discrete Mathematics, Algorithms and Applications 10, no. 02 (2018): 1850021. http://dx.doi.org/10.1142/s1793830918500210.

Full text

Abstract:

The lower bounds for the size of maximum rainbow matching in properly edge-colored graphs have been studied deeply during the last decades. An edge-coloring of a graph [Formula: see text] is called a strong edge-coloring if each path of length at most three is rainbow. Clearly, the strong edge-coloring is a natural generalization of the proper one. Recently, Babu et al. considered the problem in the strongly edge-colored graphs. In this paper, we introduce a semi-strong edge-coloring of graphs and consider the existence of large rainbow matchings in it.

APA, Harvard, Vancouver, ISO, and other styles

5

Huo, Jingjing, Mingchao Li, and Ying Wang. "A Characterization for the Neighbor-Distinguishing Index of Planar Graphs." Symmetry 14, no. 7 (2022): 1289. http://dx.doi.org/10.3390/sym14071289.

Full text

Abstract:

Symmetry, such as structural symmetry, color symmetry and so on, plays an important role in graph coloring. In this paper, we use structural symmetry and color symmetry to study the characterization for the neighbor-distinguishing index of planar graphs. Let G be a simple graph with no isolated edges. The neighbor-distinguishing edge coloring of G is a proper edge coloring of G such that any two adjacent vertices admit different sets consisting of the colors of their incident edges. The neighbor-distinguishing index χa′(G) of G is the smallest number of colors in such an edge coloring of G. It

APA, Harvard, Vancouver, ISO, and other styles

6

SKULRATTANAKULCHAI, SAN, and HAROLD N. GABOW. "COLORING ALGORITHMS ON SUBCUBIC GRAPHS." International Journal of Foundations of Computer Science 15, no. 01 (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 grap

APA, Harvard, Vancouver, ISO, and other styles

7

Bu, Yuehua, and Chentao Qi. "Injective edge coloring of sparse graphs." Discrete Mathematics, Algorithms and Applications 10, no. 02 (2018): 1850022. http://dx.doi.org/10.1142/s1793830918500222.

Full text

Abstract:

A [Formula: see text]-injective edge coloring of a graph [Formula: see text] is a coloring [Formula: see text], such that if [Formula: see text], [Formula: see text] and [Formula: see text] are consecutive edges in [Formula: see text], then [Formula: see text]. [Formula: see text] has a [Formula: see text]-injective edge coloring[Formula: see text] is called the injective edge coloring number. In this paper, we consider the upper bound of [Formula: see text] in terms of the maximum average degree mad[Formula: see text], where [Formula: see text].

APA, Harvard, Vancouver, ISO, and other styles

8

Yin, Huixin, Miaomiao Han, and Murong Xu. "Strong Edge Coloring of K4(t)-Minor Free Graphs." Axioms 12, no. 6 (2023): 556. http://dx.doi.org/10.3390/axioms12060556.

Full text

Abstract:

A strong edge coloring of a graph G is a proper coloring of edges in G such that any two edges of distance at most 2 are colored with distinct colors. The strong chromatic index χs′(G) is the smallest integer l such that G admits a strong edge coloring using l colors. A K4(t)-minor free graph is a graph that does not contain K4(t) as a contraction subgraph, where K4(t) is obtained from a K4 by subdividing edges exactly t−4 times. The paper shows that every K4(t)-minor free graph with maximum degree Δ(G) has χs′(G)≤(t−1)Δ(G) for t∈{5,6,7} which generalizes some known results on K4-minor free gr

APA, Harvard, Vancouver, ISO, and other styles

9

Zhang, Donghan. "Neighbor Sum Distinguishing Total Choosability of IC-Planar Graphs without Theta Graphs Θ2,1,2". Mathematics 9, № 7 (2021): 708. http://dx.doi.org/10.3390/math9070708.

Full text

Abstract:

A theta graph Θ2,1,2 is a graph obtained by joining two vertices by three internally disjoint paths of lengths 2, 1, and 2. A neighbor sum distinguishing (NSD) total coloring ϕ of G is a proper total coloring of G such that ∑z∈EG(u)∪{u}ϕ(z)≠∑z∈EG(v)∪{v}ϕ(z) for each edge uv∈E(G), where EG(u) denotes the set of edges incident with a vertex u. In 2015, Pilśniak and Woźniak introduced this coloring and conjectured that every graph with maximum degree Δ admits an NSD total (Δ+3)-coloring. In this paper, we show that the listing version of this conjecture holds for any IC-planar graph with maximum

APA, Harvard, Vancouver, ISO, and other styles

10

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 text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

11

Nagarathinam, R., N. Parvathi, and . "Grundy Number of Some Chordal Graphs." International Journal of Engineering & Technology 7, no. 4.10 (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

12

Ma, Hongping, Zhengke Miao, Hong Zhu, Jianhua Zhang, and Rong Luo. "Strong List Edge Coloring of Subcubic Graphs." Mathematical Problems in Engineering 2013 (2013): 1–6. http://dx.doi.org/10.1155/2013/316501.

Full text

Abstract:

We study strong list edge coloring of subcubic graphs, and we prove that every subcubic graph with maximum average degree less than 15/7, 27/11, 13/5, and 36/13 can be strongly list edge colored with six, seven, eight, and nine colors, respectively.

APA, Harvard, Vancouver, ISO, and other styles

13

Ghazaryan, A. B. "ON PALETTE INDEX OF UNICYCLE AND BICYCLE GRAPHS." Proceedings of the YSU A: Physical and Mathematical Sciences 53, no. 1 (248) (2019): 3–12. http://dx.doi.org/10.46991/pysu:a/2019.53.1.003.

Full text

Abstract:

Given a proper edge coloring $ \phi $ of a graph $ G $, we define the palette $ S_G (\nu, \phi) $ of a vertex $ \nu \mathclose{\in} V(G) $ as the set of all colors appearing on edges incident with $ \nu $. The palette index $ \check{s} (G) $ of $ G $ is the minimum number of distinct palettes occurring in a proper edge coloring of $ G $. In this paper we give an upper bound on the palette index of a graph G in terms of cyclomatic number $ cyc(G) $ of $ G $ and maximum degree $ \Delta (G) $ of $ G $. We also give a sharp upper bound for the palette index of unicycle and bicycle graphs.

APA, Harvard, Vancouver, ISO, and other styles

14

Vignesh, Radhakrishnan, Jayabalan Geetha, and Kanagasabapathi Somasundaram. "Total coloring conjecture for vertex, edge and neighborhood corona products of graphs." Discrete Mathematics, Algorithms and Applications 11, no. 01 (2019): 1950014. http://dx.doi.org/10.1142/s1793830919500149.

Full text

Abstract:

A total coloring of a graph [Formula: see text] is an assignment of colors to the elements of the graph [Formula: see text] such that no adjacent vertices and edges receive the same color. The total chromatic number of a graph [Formula: see text], denoted by [Formula: see text], is the minimum number of colors that suffice in a total coloring. Behzad and Vizing conjectured that for any simple graph [Formula: see text], [Formula: see text], where [Formula: see text] is the maximum degree of [Formula: see text]. In this paper, we prove the tight bound of the total coloring conjecture for the thr

APA, Harvard, Vancouver, ISO, and other styles

15

Mao, Yaping, Zhao Wang, Fengnan Yanling, and Chengfu Ye. "Monochromatic connectivity and graph products." Discrete Mathematics, Algorithms and Applications 08, no. 01 (2016): 1650011. http://dx.doi.org/10.1142/s1793830916500117.

Full text

Abstract:

The concept of monochromatic connectivity was introduced by Caro and Yuster. A path in an edge-colored graph is called a monochromatic path if all the edges on the path are colored the same. An edge-coloring of [Formula: see text] is a monochromatic connection coloring ([Formula: see text]-coloring, for short) if there is a monochromatic path joining any two vertices in [Formula: see text]. The monochromatic connection number, denoted by [Formula: see text], is defined to be the maximum number of colors used in an [Formula: see text]-coloring of a graph [Formula: see text]. In this paper, we s

APA, Harvard, Vancouver, ISO, and other styles

16

Chen, Zhi-Zhong, Sayuri Konno, and Yuki Matsushita. "Approximating maximum edge 2-coloring in simple graphs." Discrete Applied Mathematics 158, no. 17 (2010): 1894–901. http://dx.doi.org/10.1016/j.dam.2010.08.010.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Li, Shuchao, and Xuechao Li. "Edge coloring of graphs with small maximum degrees." Discrete Mathematics 309, no. 14 (2009): 4843–52. http://dx.doi.org/10.1016/j.disc.2008.07.006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Kostochka, Alexandr, André Raspaud, and Jingwei Xu. "Injective edge-coloring of graphs with given maximum degree." European Journal of Combinatorics 96 (August 2021): 103355. http://dx.doi.org/10.1016/j.ejc.2021.103355.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Wang, Ying, Yiqiao Wang, and Weifan Wang. "Star edge-coloring of graphs with maximum degree four." Applied Mathematics and Computation 340 (January 2019): 268–75. http://dx.doi.org/10.1016/j.amc.2018.08.035.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Basavaraju, Manu, and L. Sunil Chandran. "Acyclic edge coloring of graphs with maximum degree 4." Journal of Graph Theory 61, no. 3 (2009): 192–209. http://dx.doi.org/10.1002/jgt.20376.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Zhu, Junlei. "Injective edge coloring of graphs with maximum degree 5." Discrete Applied Mathematics 334 (July 2023): 119–26. http://dx.doi.org/10.1016/j.dam.2023.03.022.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Jumnongnit, Patcharapan, and Kittikorn Nakprasit. "Graphs with Bounded Maximum Average Degree and Their Neighbor Sum Distinguishing Total-Choice Numbers." International Journal of Mathematics and Mathematical Sciences 2017 (2017): 1–4. http://dx.doi.org/10.1155/2017/5897049.

Full text

Abstract:

Let G be a graph and ϕ:V(G)∪E(G)→{1,2,3,…,k} be a k-total coloring. Let w(v) denote the sum of color on a vertex v and colors assigned to edges incident to v. If w(u)≠w(v) whenever uv∈E(G), then ϕ is called a neighbor sum distinguishing total coloring. The smallest integer k such that G has a neighbor sum distinguishing k-total coloring is denoted by tndi∑ (G). In 2014, Dong and Wang obtained the results about tndi∑ (G) depending on the value of maximum average degree. A k-assignment L of G is a list assignment L of integers to vertices and edges with L(v)=k for each vertex v and L(e)=k for ea

APA, Harvard, Vancouver, ISO, and other styles

23

Jendrol', Stanislav, and Michaela Vrbjarová. "Maximum edge-colorings of graphs." Discussiones Mathematicae Graph Theory 36, no. 1 (2016): 117. http://dx.doi.org/10.7151/dmgt.1843.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Zhang, Baochen, Yulin Chang, Jie Hu, Meijie Ma, and Donglei Yang. "List strong edge-coloring of graphs with maximum degree 4." Discrete Mathematics 343, no. 6 (2020): 111854. http://dx.doi.org/10.1016/j.disc.2020.111854.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Lv, Jian-Bo, Xiangwen Li, and Gexin Yu. "On strong edge-coloring of graphs with maximum degree 4." Discrete Applied Mathematics 235 (January 2018): 142–53. http://dx.doi.org/10.1016/j.dam.2017.09.006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Sereni, Jean-Sébastien, and Matěj Stehlík. "Edge-face coloring of plane graphs with maximum degree nine." Journal of Graph Theory 66, no. 4 (2010): 332–46. http://dx.doi.org/10.1002/jgt.20506.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Fabrici, Igor, Mirko Horňák, and Simona Rindošová. "Facial unique-maximum edge and total coloring of plane graphs." Discrete Applied Mathematics 291 (March 2021): 171–79. http://dx.doi.org/10.1016/j.dam.2020.09.016.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

XU, CHANGQING, and GUIZHEN LIU. "ON SUPER f-EDGE COVER-COLORING IN MULTIGRAPHS." Discrete Mathematics, Algorithms and Applications 01, no. 04 (2009): 531–40. http://dx.doi.org/10.1142/s1793830909000397.

Full text

Abstract:

Given a multigraph G, an edge cover-coloring of G is called an f-edge cover-coloring, if each color appears at each vertex v at least f(v) times. Let [Formula: see text] be the maximum positive integer k for which an f-edge cover-coloring with k colors of G exists. An f-edge cover-coloring of G is called a super f-edge cover-coloring, if parallel edges receive distinct colors. Let [Formula: see text] denote the maximum positive integer k for which a super f-edge cover-coloring with k colors of G exists. A sufficient condition for a graph G to have [Formula: see text] is given.

APA, Harvard, Vancouver, ISO, and other styles

29

Chartrand, Gary, and Ping Zhang. "The Ascending Ramsey Index of a Graph." Symmetry 15, no. 2 (2023): 523. http://dx.doi.org/10.3390/sym15020523.

Full text

Abstract:

Let G be a graph with a given red-blue coloring c of the edges of G. An ascending Ramsey sequence in G with respect to c is a sequence G1, G2, …, Gk of pairwise edge-disjoint subgraphs of G such that each subgraph Gi (1≤i≤k) is monochromatic and Gi is isomorphic to a proper subgraph of Gi+1 (1≤i≤k−1). The ascending Ramsey index ARc(G) of G with respect to c is the maximum length of an ascending Ramsey sequence in G with respect to c. The ascending Ramsey index AR(G) of G is the minimum value of ARc(G) among all red-blue colorings c of G. It is shown that there is a connection between this conc

APA, Harvard, Vancouver, ISO, and other styles

30

Chao, Fugang, and Donghan Zhang. "Neighbor sum distinguishing total choice number of IC-planar graphs with restrictive conditions." AIMS Mathematics 8, no. 6 (2023): 13637–46. http://dx.doi.org/10.3934/math.2023692.

Full text

Abstract:

<abstract><p>A neighbor sum distinguishing (NSD) total coloring $ \phi $ of $ G $ is a proper total coloring such that $ \sum_{z\in E_{G}(u)\cup\{u\}}\phi(z)\neq\sum_{z\in E_{G}(v)\cup\{v\}}\phi(z) $ for each edge $ uv\in E(G) $. Pilśniak and Woźniak asserted that each graph with a maximum degree $ \Delta $ admits an NSD total $ (\Delta+3) $-coloring in 2015. In this paper, we prove that the list version of this conjecture holds for any IC-planar graph with $ \Delta\geq10 $ but without five cycles by applying the discharging method, which improves the result of Zhang (NSD list tota

APA, Harvard, Vancouver, ISO, and other styles

31

Jin, Zemin, Oothan Nweit, Kaijun Wang, and Yuling Wang. "Anti-Ramsey numbers for matchings in regular bipartite graphs." Discrete Mathematics, Algorithms and Applications 09, no. 02 (2017): 1750019. http://dx.doi.org/10.1142/s1793830917500197.

Full text

Abstract:

Let [Formula: see text] be a family of graphs. The anti-Ramsey number [Formula: see text] for [Formula: see text] in the graph [Formula: see text] is the maximum number of colors in an edge coloring of [Formula: see text] that does not have any rainbow copy of any graph in [Formula: see text]. In this paper, we consider the anti-Ramsey number for matchings in regular bipartite graphs and determine its value under several conditions.

APA, Harvard, Vancouver, ISO, and other styles

32

Huang, Danjun, and Xianxi Wu. "Equitable Coloring of IC-Planar Graphs with Girth g ≥ 7." Axioms 12, no. 9 (2023): 822. http://dx.doi.org/10.3390/axioms12090822.

Full text

Abstract:

An equitable k-coloring of a graph G is a proper vertex coloring such that the size of any two color classes differ at most 1. If there is an equitable k-coloring of G, then the graph G is said to be equitably k-colorable. A 1-planar graph is a graph that can be embedded in the Euclidean plane such that each edge can be crossed by other edges at most once. An IC-planar graph is a 1-planar graph with distinct end vertices of any two crossings. In this paper, we will prove that every IC-planar graph with girth g≥7 is equitably Δ(G)-colorable, where Δ(G) is the maximum degree of G.

APA, Harvard, Vancouver, ISO, and other styles

33

Skulrattanakulchai, San. "4-edge-coloring graphs of maximum degree 3 in linear time." Information Processing Letters 81, no. 4 (2002): 191–95. http://dx.doi.org/10.1016/s0020-0190(01)00221-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Chen, Zhi-Zhong, and Ruka Tanahashi. "Approximating maximum edge 2-coloring in simple graphs via local improvement." Theoretical Computer Science 410, no. 45 (2009): 4543–53. http://dx.doi.org/10.1016/j.tcs.2009.07.008.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Chen, Ming, Jie Hu, Xiaowei Yu, and Shan Zhou. "List strong edge coloring of planar graphs with maximum degree 4." Discrete Mathematics 342, no. 5 (2019): 1471–80. http://dx.doi.org/10.1016/j.disc.2018.10.034.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Hocquard, Hervé, та Mickaël Montassier. "Adjacent vertex-distinguishing edge coloring of graphs with maximum degree Δ". Journal of Combinatorial Optimization 26, № 1 (2012): 152–60. http://dx.doi.org/10.1007/s10878-011-9444-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

SUN, YUEFANG. "The (3, l)-Rainbow Edge-Index of Cartesian Product Graphs." Journal of Interconnection Networks 17, no. 03n04 (2017): 1741009. http://dx.doi.org/10.1142/s0219265917410092.

Full text

Abstract:

For a graph G and a vertex subset [Formula: see text] of at least two vertices, an S-tree is a subgraph T of G that is a tree with [Formula: see text]. Two S-trees are said to be edge-disjoint if they have no common edge. Let [Formula: see text] denote the maximum number of edge-disjoint S-trees in G. For an integer K with [Formula: see text], the generalized k-edge-connectivity is defined as [Formula: see text]. An S-tree in an edge-colored graph is rainbow if no two edges of it are assigned the same color. Let [Formula: see text] and l be integers with [Formula: see text], the [Formula: see

APA, Harvard, Vancouver, ISO, and other styles

38

Li and Yu. "New Bipartite Graph Techniques for Irregular Data Redistribution Scheduling." Algorithms 12, no. 7 (2019): 142. http://dx.doi.org/10.3390/a12070142.

Full text

Abstract:

For many parallel and distributed systems, automatic data redistribution improves its locality and increases system performance for various computer problems and applications. In general, an array can be distributed to multiple processing systems by using regular or irregular distributions. Some data distribution adopts BLOCK, CYCLIC, or BLOCK-CYCLIC to specify data array decomposition and distribution. On the other hand, irregular distributions specify a different-size data array distribution according to user-defined commands or procedures. In this work, we propose three bipartite graph prob

APA, Harvard, Vancouver, ISO, and other styles

39

FÜRER, MARTIN, and BALAJI RAGHAVACHARI. "PARALLEL EDGE COLORING APPROXIMATION." Parallel Processing Letters 06, no. 03 (1996): 321–29. http://dx.doi.org/10.1142/s0129626496000315.

Full text

Abstract:

Let G be a graph with n vertices and m edges and let its maximum degree be Δ. It is shown that a valid edge coloring of G using at most 2Δ−1 colors can be computed in O( log n log Δ) time using O(m+n) processors on a CREW PRAM. Based on this, for any constant c>1, a valid edge coloring for G using at most max([cΔ], Δ+1) colors can be computed in O( log 2 n) time, using O(m+n) processors. Employing different techniques, we show that it is possible to compute a Δ2 coloring in O( log * n) time, with O(m+n) processors. Also, a maximal matching of G can be computed in O( log 2 n log Δ) time usin

APA, Harvard, Vancouver, ISO, and other styles

40

Zhu, Enqiang, and Yongsheng Rao. "A Sufficient Condition for Planar Graphs of Maximum Degree 6 to be Totally 7-Colorable." Discrete Dynamics in Nature and Society 2020 (April 11, 2020): 1–8. http://dx.doi.org/10.1155/2020/3196540.

Full text

Abstract:

A total k-coloring of a graph is an assignment of k colors to its vertices and edges such that no two adjacent or incident elements receive the same color. The total coloring conjecture (TCC) states that every simple graph G has a total ΔG+2-coloring, where ΔG is the maximum degree of G. This conjecture has been confirmed for planar graphs with maximum degree at least 7 or at most 5, i.e., the only open case of TCC is that of maximum degree 6. It is known that every planar graph G of ΔG≥9 or ΔG∈7,8 with some restrictions has a total ΔG+1-coloring. In particular, in (Shen and Wang, 2009), the a

APA, Harvard, Vancouver, ISO, and other styles

41

Chen, Zhi-Zhong, Ruka Tanahashi, and Lusheng Wang. "An improved approximation algorithm for maximum edge 2-coloring in simple graphs." Journal of Discrete Algorithms 6, no. 2 (2008): 205–15. http://dx.doi.org/10.1016/j.jda.2007.08.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Cranston, Daniel W. "Strong edge-coloring of graphs with maximum degree 4 using 22 colors." Discrete Mathematics 306, no. 21 (2006): 2772–78. http://dx.doi.org/10.1016/j.disc.2006.03.053.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Miao, Lianying, and Shiyou Pang. "On the size of edge-coloring critical graphs with maximum degree 4." Discrete Mathematics 308, no. 23 (2008): 5856–59. http://dx.doi.org/10.1016/j.disc.2007.10.013.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Faber, Vance. "Linear Hypergraph Edge Coloring - Generalizations of the EFL Conjecture." Bulletin of Mathematical Sciences and Applications 17 (November 2016): 1–9. http://dx.doi.org/10.18052/www.scipress.com/bmsa.17.1.

Full text

Abstract:

Motivated by the Erdos-Faber-Lovász (EFL) conjecture for hypergraphs, we consider the edge coloring of linear hypergraphs. We discuss several conjectures for coloring linear hypergraphs that generalize both EFL and Vizing's theorem for graphs. For example, we conjecture that in a linear hypergraph of rank 3, the edge chromatic number is at most 2 times the maximum degree unless the hypergraph is the Fano plane where the number is 7. We show that for fixed rank sufficiently large and sufficiently large degree, the conjectures are true.

APA, Harvard, Vancouver, ISO, and other styles

45

Chiba, Shuya, and Yuji Nakano. "Remarks on upper and lower bounds formatching sequencibility of graphs." Filomat 30, no. 8 (2016): 2091–99. http://dx.doi.org/10.2298/fil1608091c.

Full text

Abstract:

In 2008, Alspach [The Wonderful Walecki Construction, Bull. Inst. Combin. Appl. 52 (2008) 7-20] defined the matching sequencibility of a graph G to be the largest integer k such that there exists a linear ordering of its edges so that every k consecutive edges in the linear ordering form a matching of G, which is denoted by ms(G). In this paper, we show that every graph G of size q and maximum degree ? satisfies 1/2?q/?+1? ? ms(G) ? ?q?1/??1? by using the edge-coloring of G, and we also improve this lower bound for some particular graphs. We further discuss the relationship between the matchin

APA, Harvard, Vancouver, ISO, and other styles

46

Hocquard, Hervé, and Mickaël Montassier. "Adjacent vertex-distinguishing edge coloring of graphs with maximum degree at least five." Electronic Notes in Discrete Mathematics 38 (December 2011): 457–62. http://dx.doi.org/10.1016/j.endm.2011.09.074.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Wang, Huijuan, Bin Liu, Xin Zhang, Lidong Wu, Weili Wu, and Hongwei Gao. "List edge and list total coloring of planar graphs with maximum degree 8." Journal of Combinatorial Optimization 32, no. 1 (2015): 188–97. http://dx.doi.org/10.1007/s10878-015-9870-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

HU, XIAOXUE, та YIQIAO WANG. "PLANE GRAPHS ARE ENTIRELY (Δ + 5)-CHOOSABLE". Discrete Mathematics, Algorithms and Applications 06, № 02 (2014): 1450023. http://dx.doi.org/10.1142/s1793830914500232.

Full text

Abstract:

A plane graph G is entirely k-choosable if, for every list L of colors satisfying L(x) = k for x ∈ V(G) ∪ E(G) ∪ F(G), there exists a coloring which assigns to each vertex, each edge and each face a color from its list so that any adjacent or incident elements receive different colors. In this paper, we show that every plane graph G with maximum degree Δ ≤ 5 is entirely (Δ + 5)-choosable.

APA, Harvard, Vancouver, ISO, and other styles

49

FU, JINGCHENG, GUANGHUI WANG, JIANLIANG WU, and JIN XU. "A NOTE ON EDGE WEIGHT CHOOSABILITY OF GRAPHS." Discrete Mathematics, Algorithms and Applications 06, no. 01 (2014): 1450010. http://dx.doi.org/10.1142/s1793830914500104.

Full text

Abstract:

In 2004, Karoński, Łuczak, and Thomason conjectured that the edges of any connected graph on at least 3 vertices may be weighted from the set {1, 2, 3} so that the vertices are properly colored by the sums of their incident edge weights. Bartnicki, Grytczuk and Niwcyk introduced its list version. Assign to each edge e ∈ E(G) a list of k real numbers, say L(e), and choose a weight w(e) ∈ L(e) for each e ∈ E(G). The resulting function w : E(G) → ⋃e∈E(G) L(e) is called an edge k-list-weighting. Given a graph G, the smallest k such that any assignment of lists of size k to E(G) permits an edge k-l

APA, Harvard, Vancouver, ISO, and other styles

50

Liu, Shun-yi, He-ping Zhang, Hong-liang Lu, and Yu-qing Lin. "A note on the strong edge-coloring of outerplanar graphs with maximum degree 3." Acta Mathematicae Applicatae Sinica, English Series 32, no. 4 (2016): 883–90. http://dx.doi.org/10.1007/s10255-016-0608-3.

Full text

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!