Maximal Edge-Colorings of Graphs

Meszka, Mariusz; Tyniec, Magdalena
November 2017
Graphs & Combinatorics;Nov2017, Vol. 33 Issue 6, p1451
Academic Journal
A maximal edge-coloring of a graph G of order n is a proper edge-coloring of G with $$\chi '(K_n)$$ colors such that no edge of the complement $$\overline{G}$$ of G can be attached to G without violating conditions of a proper edge-coloring. We almost completely determine sets of all sizes of graphs which admit maximal edge-colorings.


Related Articles

  • An Enumeration Scheme and Some Algebraic Properties of a Special (132)-Avoiding Class of Permutation Patterns. Ibrahim, Aminu A. // Trends in Applied Sciences Research;Jul2007, Vol. 2 Issue 4, p334 

    An elaborate enumeration procedure, including some recursion relations, has been supplied in respect of the (132)-avoiding patterns of some special class of permutation subwords. It has been discovered that the (132)-avoiding subwords of these patterns portray some useful algebraic...

  • The proof of a conjecture concerning acyclic molecular graphs with maximal Hosoya index and diameter 4. Huiqing Liu // Journal of Mathematical Chemistry;Mar2008, Vol. 43 Issue 3, p1199 

    The Hosoya index of a graph is defined as the total number of the matchings of the graph. In this paper, we solve a conjecture in Ou, J. Math. Chem, DOI: 10.1007/S10910-006-9199-1 concerning acyclic molecular graphs with maximal Hosoya index and diameter 4.

  • Note on Enomoto and Ota's Conjecture for Short Paths in Large Graphs. Hall, Martin; Magnant, Colton; Wang, Hua // Graphs & Combinatorics;Nov2014, Vol. 30 Issue 6, p1463 

    With sufficient minimum degree sum, Enomoto and Ota conjectured that for any selected set of vertices, there exists a spanning collection of disjoint paths, each starting at one of the selected vertices and each having a prescribed length. Using the Regularity Lemma, we prove that this claim...

  • The Size of Maximally Irregular Graphs and Maximally Irregular Triangle-Free Graphs. Liu, Fengxia; Zhang, Zhao; Meng, Jixiang // Graphs & Combinatorics;May2014, Vol. 30 Issue 3, p699 

    Let G be a graph. The irregularity index of G, denoted by t( G), is the number of distinct values in the degree sequence of G. For any graph G, t( G) ≤ Δ( G), where Δ( G) is the maximum degree. If t( G) = Δ( G), then G is called maximally irregular. In this paper, we give a...

  • The complexity of P4-decomposition of regular graphs and multigraphs. Diwan, Ajit A.; Dion, Justine E.; Mendell, David J.; Plantholt, Michael J.; Tipnis, Shailesh K. // Discrete Mathematics & Theoretical Computer Science (DMTCS);2015, Vol. 17 Issue 2, p63 

    Let G denote a multigraph with edge set E(G), let μ(G) denote the maximum edge multiplicity in G, and let Pκ denote the path on κ vertices. Heinrich et al.(1999) showed that P4 decomposes a connected 4-regular graph G if and only if ¦E(G)¦ is divisible by 3. We show that P4...

  • A variation of a conjecture due to Erdös and Sós. Jian Hua Yin; Jiong Sheng Li // Acta Mathematica Sinica;May2009, Vol. 25 Issue 5, p795 

    Erdös and Sós conjectured in 1963 that every graph G on n vertices with edge number e( G) > ½ ( k − 1) n contains every tree T with k edges as a subgraph. In this paper, we consider a variation of the above conjecture, that is, for n ≥ 9/2 k2 + 37/2 k+14 and every graph G on...

  • List edge and list total coloring of 1-planar graphs. Zhang, Xin; Wu, Jianliang; Liu, Guizhen // Frontiers of Mathematics in China;Oct2012, Vol. 7 Issue 5, p1005 

    A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that each 1-planar graph with maximum degree Δ is (Δ+1)-edge-choosable and (Δ+2)-total-choosable if Δ ⩾ 16, and is Δ-edge-choosable and...

  • Removable Edges and Chords of Longest Cycles in 3-Connected Graphs. Wu, Jichang; Broersma, Hajo; Kang, Haiyan // Graphs & Combinatorics;May2014, Vol. 30 Issue 3, p743 

    We verify two special cases of Thomassen's conjecture of 1976 stating that every longest cycle in a 3-connected graph contains a chord.We prove that Thomassen's conjecture is true for two classes of 3-connected graphs that have a bounded number of removable edges on or off a longest cycle. Here...

  • A Solution for the Embedding Problem for Partial Transitive Triple Systems. Rodger, C. A. // Bulletin of the London Mathematical Society;1997, Vol. 29 Issue 3, p299 

    In this paper we solve the embedding problem for partial transitive triple systems of order n and index λ, partial TTS(n, λ) s, showing that any partial TTS(n, λ) can be embedded in a TTS(v, λ) for all λ-admissible v ≥ 2n + 1. This lower bound on v is the best possible. A...

  • Colorful Isomorphic Spanning Trees in Complete Graphs. Constantine, Gregory // Annals of Combinatorics;2005, Vol. 9 Issue 2, p163 

    Can a complete graph on an even number n (> 4) of vertices be properly edge-colored with n - 1 colors in such a way that the edges can be partitioned into edge-disjoint colorful isomorphic spanning trees? A spanning treee is colorful if all n - 1 colors occur among its edges. It is proved that...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics