Relevant bibliographies by topics / Graph edge-coloring

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers

Academic literature on the topic 'Graph edge-coloring'

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 lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Graph edge-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.

Journal articles on the topic "Graph edge-coloring"

1

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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
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 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
3

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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
4

Piri, Mohammad R., and Saeid Alikhani. "Introduction to dominated edge chromatic number of a graph." Opuscula Mathematica 41, no. 2 (2021): 245–57. http://dx.doi.org/10.7494/opmath.2021.41.2.245.

Full text
Abstract:
We introduce and study the dominated edge coloring of a graph. A dominated edge coloring of a graph \(G\), is a proper edge coloring of \(G\) such that each color class is dominated by at least one edge of \(G\). The minimum number of colors among all dominated edge coloring is called the dominated edge chromatic number, denoted by \(\chi_{dom}^{\prime}(G)\). We obtain some properties of \(\chi_{dom}^{\prime}(G)\) and compute it for specific graphs. Also examine the effects on \(\chi_{dom}^{\prime}(G)\), when \(G\) is modified by operations on vertex and edge of \(G\). Finally, we consider the \(k\)-subdivision of \(G\) and study the dominated edge chromatic number of these kind of graphs.
APA, Harvard, Vancouver, ISO, and other styles
5

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
6

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
7

Furmańczyk, Hanna, Adrian Kosowski, Bernard Ries, and Paweł Żyliński. "Mixed graph edge coloring." Discrete Mathematics 309, no. 12 (June 2009): 4027–36. http://dx.doi.org/10.1016/j.disc.2008.11.033.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Adawiyah, Robiatul, Indi Izzah Makhfudloh, and Rafiantika Megahnia Prihandini. "Local edge (a, d) –antimagic coloring on sunflower, umbrella graph and its application." Alifmatika: Jurnal Pendidikan dan Pembelajaran Matematika 5, no. 1 (June 15, 2023): 70–81. http://dx.doi.org/10.35316/alifmatika.2023.v5i1.70-81.

Full text
Abstract:
Suppose a graph G = (V, E) is a simple, connected and finite graph with vertex set V(G) and an edge set E(G). The local edge antimagic coloring is a combination of local antimagic labelling and edge coloring. A mapping f∶ V (G)→ {1, 2, ..., |V (G)|} is called local edge antimagic coloring if every two incident edges e_1and e_2, then the edge weights of e_1and e_2 maynot be the same, w(e_1) ≠ w(e_2), with e = uv ∈ G, w(e) = f(u)+ f(v) with the rule that the edges e are colored according to their weights, w_e. Local edge antimagic coloring has developed into local (a,d)-antimagic coloring. Local antimagic coloring is called local (a,d)-antimagic coloring if the set of edge weights forms an arithmetic sequence with a as an initial value and d as a difference value. The graphs used in this study are sunflower graphs and umbrella graphs. This research will also discuss one of the applications of local edge (a,d)-antimagic coloring, namely the design of the Sidoarjo line batik motif. The result show that χ_le(3,1) (Sf_n) = 3n and χ_le(3n/2,1) (U_(m,n) ) = m+1 . The local (a,d)-antimagic coloring is formed into a batik motif design with characteristics from the Sidoarjo region.
APA, Harvard, Vancouver, ISO, and other styles
9

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
10

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 text
Abstract:
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 .
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Graph edge-coloring"

1

Beşeri, Tina Ufuktepe Ünal. "Edge Coloring of A Graph/." [s.l.]: [s.n.], 2004. http://library.iyte.edu.tr/tezler/master/matematik/T000439.pdf.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Gajewar, Amita Surendra. "Approximate edge 3-coloring of cubic graphs." Thesis, Atlanta, Ga. : Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/29735.

Full text
Abstract:
Thesis (M. S.)--Computing, Georgia Institute of Technology, 2009.
Committee Chair: Prof. Richard Lipton; Committee Member: Prof. Dana Randall; Committee Member: Prof. H. Venkateswaran. Part of the SMARTech Electronic Thesis and Dissertation Collection.
APA, Harvard, Vancouver, ISO, and other styles
3

Clark, David. "Algebraic Analysis of Vertex-Distinguishing Edge-Colorings." Thesis, University of Waterloo, 2006. http://hdl.handle.net/10012/1053.

Full text
Abstract:
Vertex-distinguishing edge-colorings (vdec colorings) are a restriction of proper edge-colorings. These special colorings require that the sets of edge colors incident to every vertex be distinct. This is a relatively new field of study. We present a survey of known results concerning vdec colorings. We also define a new matrix which may be used to study vdec colorings, and examine its properties. We find several bounds on the eigenvalues of this matrix, as well as results concerning its determinant, and other properties. We finish by examining related topics and open problems.
APA, Harvard, Vancouver, ISO, and other styles
4

Casselgren, Carl Johan. "On some graph coloring problems." Doctoral thesis, Umeå universitet, Institutionen för matematik och matematisk statistik, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-43389.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Renman, Jonatan. "One-sided interval edge-colorings of bipartite graphs." Thesis, Linköpings universitet, Matematik och tillämpad matematik, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-171753.

Full text
Abstract:
A graph is an ordered pair composed by a set of vertices and a set of edges, the latter consisting of unordered pairs of vertices. Two vertices in such a pair are each others neighbors. Two edges are adjacent if they share a common vertex. Denote the amount of edges that share a specific vertex as the degree of the vertex. A proper edge-coloring of a graph is an assignment of colors from some finite set, to the edges of a graph where no two adjacent edges have the same color. A bipartition (X,Y) of a set of vertices V is an ordered pair of two disjoint sets of vertices such that V is the union of X and Y, where all the vertices in X only have neighbors in Y and vice versa. A bipartite graph is a graph whose vertices admit a bipartition (X,Y). Let G be one such graph. An X-interval coloring of G is a proper edge coloring where the colors of the edges incident to each vertex in X form an interval of integers. Denote by χ'int(G,X) the least number of colors needed for an X-interval coloring of G. In this paper we prove that if G is a bipartite graph with maximum degree 3n (n is a natural number), where all the vertices in X have degree 3, then
APA, Harvard, Vancouver, ISO, and other styles
6

McClain, Christopher. "Edge colorings of graphs and multigraphs." Columbus, Ohio : Ohio State University, 2008. http://rave.ohiolink.edu/etdc/view?acc%5Fnum=osu1211904033.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

MATTIOLO, DAVIDE. "Nowhere-zero Circular Flows e Fattori di Grafi - Costruzioni e Controesempi." Doctoral thesis, Università degli studi di Modena e Reggio Emilia, 2021. http://hdl.handle.net/11380/1237623.

Full text
Abstract:
Uno dei campi di ricerca di grande interesse nella teoria dei grafi strutturale è quello dei nowhere-zero integer flows. Una delle ragioni principali è il fatto che questi oggetti generalizzano il concetto di colorazione propria sulle facce di grafi planari. Si ricordi il Teorema dei 4-Colori del 1976, uno dei teoremi più famosi della teoria dei grafi, che afferma che ogni grafo planare senza ponti ammette una 4-colorazione propria sulle facce. Nel 1954, Tutte dimostrò che un grafo planare ammette una k-colorazione propria sulle facce se e solo se ammette un nowhere-zero k-flow e congetturò che ogni grafo senza ponti ammette un nowhere-zero 5-flow. Questa congettura, conosciuta come la Congettura dei 5-Flussi di Tutte, è uno dei problemi aperti più importanti in quest'area della matematica. È ben noto che la Congettura sui 5-Flussi è equivalente alla sua restrizione agli snarks, grafi cubici che non ammettono una 3-colorazione propria sugli spigoli e con ulteriori restrizioni sulla cintura e connettività ciclica. Molte altre congetture importanti possono essere ridotte alla classe degli snarks e questo è uno dei motivi principali per cui questi grafi sono studiati in molti articoli. In questa tesi studiamo i nowhere-zero circular flows, che sono una generalizzazione dei nowhere-zero integer flows, e, in particolare, studiamo il numero di flusso circolare di grafi. Infatti, negli ultimi decenni, i nowhere-zero circular flows hanno attratto molti autori ed ora, in questo campo, si trovano parecchi problemi di ricerca e congetture aperte. I risultati presentati in questa tesi sono motivati da queste nuove congetture, che in alcuni casi risolviamo in modo parziale o completo. La maggior parte di tali risultati sono costruzioni di famiglie infinite di snarks e, più in generale, grafi con determinate proprietà strutturali. Sottolineiamo che alcune famiglie presentate sono i primi esempi noti aventi determinate caratteristiche mentre altre contengono controesempi a problemi aperti.
Nowhere-zero integer flows in graphs represent a research field of great interest in structural graph theory. One of the main reasons is the fact that they generalize the concept of face-coloring of planar graphs. Recall that one of the most famous theorems of graph theory is for sure the 4-Color Theorem (1976), claiming that every bridgeless planar graph admits a proper face-4-coloring. In 1954, Tutte proved that a planar graph has a proper face-k-coloring if and only if it has a nowhere-zero k-flow and conjectured that every bridgeless graph admits a nowhere-zero 5-flow. This conjecture is known as the 5-Flow Conjecture and is one of the most important and outstanding open problems in this area of mathematics. It is well known that the 5-Flow Conjecture is equivalent to its restriction to snarks, that are non-3-edge-colorable cubic graphs with further technical requirements on the girth and cyclic edge-connectivity. Many other important long-standing conjectures can be reduced to the family of snarks and this is the main reason why snarks are studied in many papers. In this dissertation, we study nowhere-zero circular flows, that are a generalization of nowhere-zero integer flows, and, in particular, we study the circular flow number of graphs. Indeed, in the last decades, circular flows have attracted many authors and now some problems and conjectures are left open in this field. The results that appear in the present thesis are motivated by these new problems and conjectures, which in some cases we partially or fully answer to. Most of such results are constructions of infinite families of snarks and, more generally, graphs having specific structural properties. We remark that a few of such families are the first known examples having certain properties, and others contain counterexamples to open research problems.
APA, Harvard, Vancouver, ISO, and other styles
8

Tahraoui, Mohammed Amin. "Coloring, packing and embedding of graphs." Phd thesis, Université Claude Bernard - Lyon I, 2012. http://tel.archives-ouvertes.fr/tel-00995041.

Full text
Abstract:
In this thesis, we investigate some problems in graph theory, namelythe graph coloring problem, the graph packing problem and tree pattern matchingfor XML query processing. The common point between these problems is that theyuse labeled graphs.In the first part, we study a new coloring parameter of graphs called the gapvertex-distinguishing edge coloring. It consists in an edge-coloring of a graph G whichinduces a vertex distinguishing labeling of G such that the label of each vertex isgiven by the difference between the highest and the lowest colors of its adjacentedges. The minimum number of colors required for a gap vertex-distinguishing edgecoloring of G is called the gap chromatic number of G and is denoted by gap(G).We will compute this parameter for a large set of graphs G of order n and we evenprove that gap(G) 2 fn E 1; n; n + 1g.In the second part, we focus on graph packing problems, which is an area ofgraph theory that has grown significantly over the past several years. However, themajority of existing works focuses on unlabeled graphs. In this thesis, we introducefor the first time the packing problem for a vertex labeled graph. Roughly speaking,it consists of graph packing which preserves the labels of the vertices. We studythe corresponding optimization parameter on several classes of graphs, as well asfinding general bounds and characterizations.The last part deal with the query processing of a core subset of XML query languages:XML twig queries. An XML twig query, represented as a small query tree,is essentially a complex selection on the structure of an XML document. Matching atwig query means finding all the occurrences of the query tree embedded in the XMLdata tree. Many holistic twig join algorithms have been proposed to match XMLtwig pattern. Most of these algorithms find twig pattern matching in two steps. Inthe first one, a query tree is decomposed into smaller pieces, and solutions againstthese pieces are found. In the second step, all of these partial solutions are joinedtogether to generate the final solutions. In this part, we propose a novel holistictwig join algorithm, called TwigStack++, which features two main improvementsin the decomposition and matching phase. The proposed solutions are shown to beefficient and scalable, and should be helpful for the future research on efficient queryprocessing in a large XML database.
APA, Harvard, Vancouver, ISO, and other styles
9

Hocquard, Hervé. "Colorations de graphes sous contraintes." Phd thesis, Université Sciences et Technologies - Bordeaux I, 2011. http://tel.archives-ouvertes.fr/tel-00987686.

Full text
Abstract:
Dans cette thèse, nous nous intéressons à différentes notions de colorations sous contraintes. Nous nous intéressons plus spécialement à la coloration acyclique, à la coloration forte d'arêtes et à la coloration d'arêtes sommets adjacents distinguants.Dans le Chapitre 2, nous avons étudié la coloration acyclique. Tout d'abord nous avons cherché à borner le nombre chromatique acyclique pour la classe des graphes de degré maximum borné. Ensuite nous nous sommes attardés sur la coloration acyclique par listes. La notion de coloration acyclique par liste des graphes planaires a été introduite par Borodin, Fon-Der Flaass, Kostochka, Raspaud et Sopena. Ils ont conjecturé que tout graphe planaire est acycliquement 5-liste coloriable. De notre côté, nous avons proposé des conditions suffisantes de 3-liste coloration acyclique des graphes planaires. Dans le Chapitre 3, nous avons étudié la coloration forte d'arêtes des graphes subcubiques en majorant l'indice chromatique fort en fonction du degré moyen maximum. Nous nous sommes également intéressés à la coloration forte d'arêtes des graphes subcubiques sans cycles de longueurs données et nous avons également obtenu une majoration optimale de l'indice chromatique fort pour la famille des graphes planaires extérieurs. Nous avons aussi présenté différents résultats de complexité pour la classe des graphes planaires subcubiques. Enfin, au Chapitre 4, nous avons abordé la coloration d'arêtes sommets adjacents distinguants en déterminant les majorations de l'indice avd-chromatique en fonction du degré moyen maximum. Notre travail s'inscrit dans la continuité de celui effectué par Wang et Wang en 2010. Plus précisément, nous nous sommes focalisés sur la famille des graphes de degré maximum au moins 5.
APA, Harvard, Vancouver, ISO, and other styles
10

Kurt, Oguz. "On The Coloring of Graphs." The Ohio State University, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=osu1262287401.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Books on the topic "Graph edge-coloring"

1

Stiebitz, Michael. Graph edge coloring: Vizing's theorem and Goldberg's conjecture. Hoboken, NJ: Wiley, 2012.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

1949-, Rödl Vojtěch, Ruciński Andrzej, and Tetali Prasad, eds. A Sharp threshold for random graphs with a monochromatic triangle in every edge coloring. Providence, R.I: American Mathematical Society, 2006.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
3

Toft, Bjarne, Michael Stiebitz, Diego Scheide, and Lene M. Favrholdt. Graph Edge Coloring. Wiley & Sons, Incorporated, John, 2012.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
4

Toft, Bjarne, Michael Stiebitz, Diego Scheide, and Lene M. Favrholdt. Graph Edge Coloring: Vizing's Theorem and Goldberg's Conjecture. Wiley & Sons, Incorporated, John, 2014.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
5

Toft, Bjarne, Michael Stiebitz, Diego Scheide, and Lene M. Favrholdt. Graph Edge Coloring: Vizing's Theorem and Goldberg's Conjecture. Wiley & Sons, Incorporated, John, 2012.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
6

Toft, Bjarne, Michael Stiebitz, Diego Scheide, and Lene M. Favrholdt. Graph Edge Coloring: Vizing's Theorem and Goldberg's Conjecture. Wiley & Sons, Incorporated, John, 2012.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
7

Toft, Bjarne, Michael Stiebitz, Diego Scheide, and Lene M. Favrholdt. Graph Edge Coloring: Vizing's Theorem and Goldberg's Conjecture. Wiley & Sons, Incorporated, John, 2012.

Find full text
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Graph edge-coloring"

1

Caragiannis, Ioannis, Afonso Ferreira, Christos Kaklamanis, Stéphane Pérennes, Pino Persiano, and Hervé Rivano. "Approximate Constrained Bipartite Edge Coloring." In Graph-Theoretic Concepts in Computer Science, 21–31. Berlin, Heidelberg: Springer Berlin Heidelberg, 2001. http://dx.doi.org/10.1007/3-540-45477-2_4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Kowalik, Łukasz. "Improved Edge-Coloring with Three Colors." In Graph-Theoretic Concepts in Computer Science, 90–101. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006. http://dx.doi.org/10.1007/11917496_9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Bonamy, Marthe, Nicolas Bousquet, and Hervé Hocquard. "Adjacent vertex-distinguishing edge coloring of graphs." In The Seventh European Conference on Combinatorics, Graph Theory and Applications, 313–18. Pisa: Scuola Normale Superiore, 2013. http://dx.doi.org/10.1007/978-88-7642-475-5_50.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Izza, Rifda, Dafik, Arika Indah Kristiana, Ika Hesti Agustin, Ika Nur Maylisa, and Elsa Yuli Kurniawati. "On Local (a, d)-Edge Antimagic Coloring of Some Graphs." In Proceedings of the 6th International Conference on Combinatorics, Graph Theory, and Network Topology (ICCGANT 2022), 30–41. Dordrecht: Atlantis Press International BV, 2023. http://dx.doi.org/10.2991/978-94-6463-138-8_4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Regts, Guus. "A characterization of edge-reflection positive partition functions of vertex-coloring models." In The Seventh European Conference on Combinatorics, Graph Theory and Applications, 305–11. Pisa: Scuola Normale Superiore, 2013. http://dx.doi.org/10.1007/978-88-7642-475-5_49.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Putra, Eric Dwi, Dafik, Arika Indah Kristiana, Robiatul Adawiyah, and Rafiantika Megahnia Prihandini. "On Local (a, d)-Edge Antimagic Coloring of Some Specific Classes of Graphs." In Proceedings of the 6th International Conference on Combinatorics, Graph Theory, and Network Topology (ICCGANT 2022), 42–53. Dordrecht: Atlantis Press International BV, 2023. http://dx.doi.org/10.2991/978-94-6463-138-8_5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Soifer, Alexander. "Edge Chromatic Number of a Graph." In The Mathematical Coloring Book, 127–39. New York, NY: Springer New York, 2009. http://dx.doi.org/10.1007/978-0-387-74642-5_16.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Huang, Zhepeng, Long Yuan, Haofei Sui, Zi Chen, Shiyu Yang, and Jianye Yang. "Edge Coloring on Dynamic Graphs." In Database Systems for Advanced Applications, 137–53. Cham: Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-30675-4_10.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Zhou, Xiao, and Takao Nishizeki. "Edge-coloring and f-coloring for various classes of graphs." In Algorithms and Computation, 199–207. Berlin, Heidelberg: Springer Berlin Heidelberg, 1994. http://dx.doi.org/10.1007/3-540-58325-4_182.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Jin, Xin, Min Chen, Xinhong Pang, and Jingjing Huo. "Edge-Face List Coloring of Halin Graphs." In Algorithmic Aspects in Information and Management, 481–91. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-57602-8_43.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Graph edge-coloring"

1

Sobral, Gabriel A. G., Marina Groshaus, and André L. P. Guedes. "Biclique edge-choosability in some classes of graphs∗." In II Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2017. http://dx.doi.org/10.5753/etc.2017.3203.

Full text
Abstract:
In this paper we study the problem of coloring the edges of a graph for any k-list assignment such that there is no maximal monochromatic biclique, in other words, the k-biclique edge-choosability problem. We prove that the K3free graphs that are not odd cycles are 2-star edge-choosable, chordal bipartite graphs are 2-biclique edge-choosable and we present a lower bound for the biclique choice index of power of cycles and power of paths. We also provide polynomial algorithms to compute a 2-biclique (star) edge-coloring for K3-free and chordal bipartite graphs for any given 2-list assignment to edges.
APA, Harvard, Vancouver, ISO, and other styles
2

Hebrard, Emmanuel, and George Katsirelos. "Clause Learning and New Bounds for Graph Coloring." In Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}. California: International Joint Conferences on Artificial Intelligence Organization, 2019. http://dx.doi.org/10.24963/ijcai.2019/856.

Full text
Abstract:
Graph coloring is a major component of numerous allocation and scheduling problems. We introduce a hybrid CP/SAT approach to graph coloring based on exploring Zykov’s tree: for two non-neighbors, either they take a different color and there might as well be an edge between them, or they take the same color and we might as well merge them. Branching on whether two neighbors get the same color yields a symmetry-free tree with complete graphs as leaves, which correspond to colorings of the original graph. We introduce a new lower bound for this problem based on Mycielskian graphs; a method to produce a clausal explanation of this bound for use in a CDCL algorithm; and a branching heuristic emulating Brelaz on the Zykov tree. The combination of these techniques in a branch- and-bound search outperforms Dsatur and other SAT-based approaches on standard benchmarks both for finding upper bounds and for proving lower bounds.
APA, Harvard, Vancouver, ISO, and other styles
3

Razak, Hafizah A., Zaidah Ibrahim, and Naimah Mohd Hussin. "Bipartite graph edge coloring approach to course timetabling." In Knowledge Management (CAMP). IEEE, 2010. http://dx.doi.org/10.1109/infrkm.2010.5466912.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Rocha, Aleffer, Sheila M. Almeida, and Leandro M. Zatesko. "The Rainbow Connection Number of Triangular Snake Graphs." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2020. http://dx.doi.org/10.5753/etc.2020.11091.

Full text
Abstract:
Rainbow coloring problems, of noteworthy applications in Information Security, have been receiving much attention last years in Combinatorics. The rainbow connection number of a graph G is the least number of colors for a (not necessarily proper) edge coloring of G such that between any pair of vertices there is a path whose edge colors are all distinct. In this paper we determine the rainbow connection number of the triple triangular snake graphs.
APA, Harvard, Vancouver, ISO, and other styles
5

Jiao, Susu, Shuangliang Tian, Xiahong Cai, and Huan Yang. "The k-distance coloring and k-distance edge coloring on double graph of paths." In 2017 Global Conference on Mechanics and Civil Engineering (GCMCE 2017). Paris, France: Atlantis Press, 2017. http://dx.doi.org/10.2991/gcmce-17.2017.17.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Ji-mao, Zhuoma, and Gang Ma. "On the Vertex-Distinguishing Equitable Edge Coloring of Product Graph." In 2019 International Conference on Electronic Engineering and Informatics (EEI). IEEE, 2019. http://dx.doi.org/10.1109/eei48997.2019.00099.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Kang, Yumei, Jingwen Li, Qinghou Yuan, and Shuai Sun. "Adjacent vertex sum reducible edge coloring algorithm based on graph cryptography." In 2020 IEEE 9th Joint International Information Technology and Artificial Intelligence Conference (ITAIC). IEEE, 2020. http://dx.doi.org/10.1109/itaic49862.2020.9339087.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Karpov, Dmitry Valerievich. "On images on plane and colorings of k-planar graphs." In Academician O.B. Lupanov 14th International Scientific Seminar "Discrete Mathematics and Its Applications". Keldysh Institute of Applied Mathematics, 2022. http://dx.doi.org/10.20948/dms-2022-5.

Full text
Abstract:
A graph is called k-planar if it can be drawn on the plane in such a way that each edge intersects at most k others. Probably, for the first time such a generalization appeared in the work of Ringel in 1965 - 1-planar graphs were considered there and it was proved that any such graph has a regular coloring of vertices in 7 colors. Later, k-planar graphs were defined for all natural k, questions about the estimate for the number of edges in such graphs, the estimate for the chromatic number, and various questions about their images on the plane were studied. The report will talk about classical and modern results from this area.
APA, Harvard, Vancouver, ISO, and other styles
9

Garvardt, Jaroslav, Niels Grüttemeier, Christian Komusiewicz, and Nils Morawietz. "Parameterized Local Search for Max c-Cut." In Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}. California: International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/620.

Full text
Abstract:
In the NP-hard Max c-Cut problem, one is given an undirected edge-weighted graph G and wants to color the vertices of G with c colors such that the total weight of edges with distinctly colored endpoints is maximal. The case with c=2 is the famous Max Cut problem. To deal with the NP-hardness of this problem, we study parameterized local search algorithms. More precisely, we study LS-Max c-Cut where we are additionally given a vertex coloring f and an integer k and the task is to find a better coloring f' that differs from f in at most k entries, if such a coloring exists; otherwise, f is k-optimal. We show that LS-Max c-Cut presumably cannot be solved in g(k) · nᴼ⁽¹⁾ time even on bipartite graphs, for all c ≥ 2. We then show an algorithm for LS-Max c-Cut with running time O((3eΔ)ᵏ · c · k³ · Δ · n), where Δ is the maximum degree of the input graph. Finally, we evaluate the practical performance of this algorithm in a hill-climbing approach as a post-processing for state-of-the-art heuristics for Max c-Cut. We show that using parameterized local search, the results of this heuristic can be further improved on a set of standard benchmark instances.
APA, Harvard, Vancouver, ISO, and other styles
10

Bahmani, Bahman, Aranyak Mehta, and Rajeev Motwani. "A 1.43-Competitive Online Graph Edge Coloring Algorithm In The Random Order Arrival Model." In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2010. http://dx.doi.org/10.1137/1.9781611973075.4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Graph edge-coloring' for particular source types:
Journal articles Dissertations / Theses
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!

To the bibliography