TITLE

Maximal Edge-Colorings of Graphs

AUTHOR(S)
Meszka, Mariusz; Tyniec, Magdalena
PUB. DATE
November 2017
SOURCE
Graphs & Combinatorics;Nov2017, Vol. 33 Issue 6, p1451
SOURCE TYPE
DOC. TYPE
Article
ABSTRACT
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.
ACCESSION #
126308059

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

Share